Randomized online algorithms for minimum metric bipartite matching

DOI10.1145/1109557.1109662zbMath1192.68860OpenAlexW4242517206MaRDI QIDQ3581513

Akash Nanavati, Adam Meyerson, Laura Poplawski

Publication date: 16 August 2010

Published in: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1109557.1109662

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items (20)

Minimum Cost Perfect Matching with Delays for Two Sources ⋮ Minimum cost perfect matching with delays for two sources ⋮ A randomized algorithm for the on-line weighted bipartite matching problem ⋮ A poly-log competitive posted-price algorithm for online metrical matching on a spider ⋮ Online Matching in Regular Bipartite Graphs ⋮ Online minimum matching with uniform metric and random arrivals ⋮ A \(o(n)\)-competitive deterministic algorithm for online matching on a line ⋮ An optimally-competitive algorithm for maximum online perfect bipartite matching with i.i.d. arrivals ⋮ Online bottleneck matching on a line ⋮ Online semi-matching problem with two heterogeneous sensors in a metric space ⋮ Truthful facility assignment with resource augmentation: an exact analysis of serial dictatorship ⋮ Online Matching in Regular Bipartite Graphs with Randomized Adversary ⋮ A randomized \(O(\log^2k)\)-competitive algorithm for metric bipartite matching ⋮ Permutation Strikes Back: The Power of Recourse in Online Metric Matching ⋮ Deterministic min-cost matching with delays ⋮ Competitive analysis for two variants of online metric matching problem ⋮ Greedy metric minimum online matchings with random arrivals ⋮ Impatient Online Matching ⋮ Stochastic Online Metric Matching ⋮ Competitive strategies for an online generalized assignment problem with a service consecution constraint

This page was built for publication: Randomized online algorithms for minimum metric bipartite matching