Search: onr:"swepub:oai:research.chalmers.se:2a007afe-ff1e-4484-847d-7622b4602f0e" >
Greediness is not a...
Abstract
Subject headings
Close
- Finding a maximum-weight matching is a classical and well-studied problem in computer science, solvable in cubic time in general graphs. We introduce and consider in this work the “discovery” variant of the bipartite matching problem (or assignment problem) where edge weights are not provided as input but must be queried, requiring additional and costly computations. Hence, discovery algorithms are developed aiming to minimize the number of queried weights while providing guarantees on the computed solution. We show in this work the hardness of the underlying problem in general while providing several efficient algorithms that can make use of natural assumptions about the order in which the nodes are processed by the greedy algorithms. Our motivations for exploring this problem stem from finding practical solutions to maximum-weight matching in hypergraphs, a problem recently emerging in the formation of peer-to-peer energy sharing communities.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Keyword
- query complexity
- greedy algorithms
- assignment problem
- discovery algorithms
Publication and Content Type
- kon (subject category)
- ref (subject category)
Find in a library
To the university's database