Randomized online algorithms for minimum metric bipartite matching

DOI10.1145/1109557.1109662MaRDI QIDQ3581513zbMATH OpenOpenAlexFDO

Authors Adam Meyerson, Akash Nanavati, 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)

Cited in

(26)

• Minimum cost perfect matching with delays for two sources
• A poly-log competitive posted-price algorithm for online metrical matching on a spider
• An optimally-competitive algorithm for maximum online perfect bipartite matching with i.i.d. arrivals
• Greedy metric minimum online matchings with random arrivals
• Competitive strategies for an online generalized assignment problem with a service consecution constraint
• A \(o(n)\)-competitive deterministic algorithm for online matching on a line
• Online minimum matching with uniform metric and random arrivals
• A randomized O(^2k)-competitive algorithm for metric bipartite matching
• Competitive analysis for two variants of online metric matching problem
• Online matching in regular bipartite graphs
• Impatient Online Matching
• Stochastic online metric matching
• Minimum cost perfect matching with delays for two sources
• Permutation Strikes Back: The Power of Recourse in Online Metric Matching
• 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 algorithm for online metric b-matching
• An O( n)-competitive posted-price algorithm for online matching on the line
• Randomized algorithm for MPMD on two sources
• Capacity-insensitive algorithms for online facility assignment problems on a line
• Maximizing rides served for dial-a-ride on the uniform metric
• Stochastic online metric matching: adversarial is no harder than stochastic
• A nearly optimal deterministic algorithm for online transportation problem
• A randomized algorithm for the on-line weighted bipartite matching problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3581513)