An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions

DOI10.1007/978-3-642-40450-4_50zbMath1394.68448OpenAlexW122351777WikidataQ57408006 ScholiaQ57408006MaRDI QIDQ2849348

Berthold Vöcking, Andreas Tönnis, Thomas Kesselheim, Klaus Radke

Publication date: 17 September 2013

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-40450-4_50

Mathematics Subject Classification ID

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Auctions, bargaining, bidding and selling, and other market models (91B26) Graph algorithms (graph-theoretic aspects) (05C85) Online algorithms; streaming algorithms (68W27)

Related Items (33)

Secretary Markets with Local Information ⋮ Online crowdsourced truck delivery using historical information ⋮ The Temp Secretary Problem ⋮ Primal Beats Dual on Online Packing LPs in the Random-Order Model ⋮ The secretary recommendation problem ⋮ A Framework for the Secretary Problem on the Intersection of Matroids ⋮ A note on the online interval scheduling secretary problem ⋮ Near optimal algorithms for online weighted bipartite matching in adversary model ⋮ An optimally-competitive algorithm for maximum online perfect bipartite matching with i.i.d. arrivals ⋮ Approximation algorithms for stochastic online matching with reusable resources ⋮ Constant-competitiveness for random assignment matroid secretary without knowing the matroid ⋮ Packing returning secretaries ⋮ Secretary and online matching problems with machine learned advice ⋮ Unnamed Item ⋮ Knapsack secretary through boosting ⋮ Algorithms for Online Matching, Assortment, and Pricing with Tight Weight-Dependent Competitive Ratios ⋮ Improved Online Algorithms for Knapsack and GAP in the Random Order Model ⋮ Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints ⋮ On extensions of the deterministic online model for bipartite matching and max-sat ⋮ Buyback problem with discrete concave valuation functions ⋮ Stable secretaries ⋮ Online stochastic matching: new algorithms and bounds ⋮ Secretary markets with local information ⋮ Unnamed Item ⋮ Prior independent mechanisms via prophet inequalities with limited information ⋮ Improved online algorithms for Knapsack and GAP in the random order model ⋮ The Matroid Secretary Problem for Minor-Closed Classes and Random Matroids ⋮ A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem ⋮ Online Vertex-Weighted Bipartite Matching ⋮ Strong Algorithms for the Ordinal Matroid Secretary Problem ⋮ Improved online algorithm for fractional knapsack in the random order model ⋮ Learn from history for online bipartite matching ⋮ Online generalized assignment problem with historical information

This page was built for publication: An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions