On-line algorithms for weighted bipartite matching and stable marriages
From MaRDI portal
Publication:1342235
DOI10.1016/0304-3975(94)90042-6zbMath0938.68934OpenAlexW2093153678WikidataQ126778268 ScholiaQ126778268MaRDI QIDQ1342235
Stephen G. Mitchell, Samir Khuller, Vijay V. Vazirani
Publication date: 9 February 1995
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(94)90042-6
Related Items (44)
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 ⋮ Stable Marriage and Roommates Problems with Restricted Edges: Complexity and Approximability ⋮ A poly-log competitive posted-price algorithm for online metrical matching on a spider ⋮ A $$o(n)$$-Competitive Deterministic Algorithm for Online Matching on a Line ⋮ Serve or skip: the power of rejection in online bottleneck matching ⋮ A \(o(n)\)-competitive deterministic algorithm for online matching on a line ⋮ Subquadratic algorithms for succinct stable matching ⋮ An optimally-competitive algorithm for maximum online perfect bipartite matching with i.i.d. arrivals ⋮ Matching on the Line Admits no \(o(\sqrt {\log n})\) -Competitive Algorithm ⋮ On the advice complexity of online bipartite matching and online stable marriage ⋮ Online 2-stage stable matching ⋮ Computing relaxations for the three-dimensional stable matching problem with cyclic preferences ⋮ Online Metric Algorithms with Untrusted Predictions ⋮ Dynamic Stochastic Matching Under Limited Time ⋮ The online transportation problem ⋮ 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 ⋮ ``Almost stable matchings in the roommates problem with bounded preference lists ⋮ Improved bounds for randomized preemptive online matching ⋮ Online bottleneck matching ⋮ Unnamed Item ⋮ Almost stable matchings by truncating the Gale-Shapley algorithm ⋮ A randomized \(O(\log^2k)\)-competitive algorithm for metric bipartite matching ⋮ Improved Online Algorithms for Knapsack and GAP in the Random Order Model ⋮ Local Matching Dynamics in Social Networks ⋮ Permutation Strikes Back: The Power of Recourse in Online Metric Matching ⋮ Stable marriage and roommates problems with restricted edges: complexity and approximability ⋮ Stable secretaries ⋮ Size versus stability in the marriage problem ⋮ Unnamed Item ⋮ Size Versus Stability in the Marriage Problem ⋮ Online facility assignment ⋮ Improved online algorithms for Knapsack and GAP in the random order model ⋮ Competitive analysis for two variants of online metric matching problem ⋮ Greedy metric minimum online matchings with random arrivals ⋮ Unnamed Item ⋮ Impatient Online Matching ⋮ Stochastic Online Metric Matching ⋮ An optimal deterministic algorithm for online \(b\)-matching ⋮ Competitive strategies for an online generalized assignment problem with a service consecution constraint ⋮ The hospitals/residents problem with lower quotas
Cites Work
This page was built for publication: On-line algorithms for weighted bipartite matching and stable marriages
