2013 | OriginalPaper | Buchkapitel
An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions
verfasst von : Thomas Kesselheim, Klaus Radke, Andreas Tönnis, Berthold Vöcking
Erschienen in: Algorithms – ESA 2013
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We study online variants of weighted bipartite matching on graphs and hypergraphs. In our model for online matching, the vertices on the right-hand side of a bipartite graph are given in advance and the vertices on the left-hand side arrive online in random order. Whenever a vertex arrives, its adjacent edges with the corresponding weights are revealed and the online algorithm has to decide which of these edges should be included in the matching. The studied matching problems have applications, e.g., in online ad auctions and combinatorial auctions where the right-hand side vertices correspond to items and the left-hand side vertices to bidders.
Our main contribution is an optimal algorithm for the weighted matching problem on bipartite graphs. The algorithm is a natural generalization of the classical algorithm for the secretary problem achieving a competitive ratio of e ≈ 2.72 which matches the well-known upper and lower bound for the secretary problem. This shows that the classic algorithmic approach for the secretary problem can be extended from the simple selection of a best possible singleton to a rich combinatorial optimization problem.
On hypergraphs with (
d
+ 1)-uniform hyperedges, corresponding to combinatorial auctions with bundles of size
d
, we achieve competitive ratio
O
(
d
) in comparison to the previously known ratios
$O\big(d^2\big)$
and
O
(
d
log
m
), where
m
is the number of items. Additionally, we study variations of the hypergraph matching problem representing combinatorial auctions for items with bounded multiplicities or for bidders with submodular valuation functions. In particular for the case of submodular valuation functions we improve the competitive ratio from
O
(log
m
) to e.