Online Weighted Matching
From MaRDI portal
Publication:4696653
DOI10.1006/jagm.1993.1026zbMath0768.68151OpenAlexW1978382073MaRDI QIDQ4696653
Bala Kalyanasundaram, Kirk R. Pruhs
Publication date: 29 June 1993
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/f17dc03b86620e4a0bdfe9656f9a7151104c1ccf
Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items (46)
Minimum Cost Perfect Matching with Delays for Two Sources ⋮ Average performance of a greedy algorithm for the on-line minimum matching problem on Euclidean space ⋮ Minimum cost perfect matching with delays for two sources ⋮ A randomized algorithm for the on-line weighted bipartite matching problem ⋮ On-line algorithms for weighted bipartite matching and stable marriages ⋮ 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 ⋮ 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 ⋮ Matching on the Line Admits no \(o(\sqrt {\log n})\) -Competitive Algorithm ⋮ Online Metric Algorithms with Untrusted Predictions ⋮ Dynamic Stochastic Matching Under Limited Time ⋮ Algorithms for online car-sharing problem ⋮ The online transportation problem ⋮ On-line maximum matching in complete multi-partite graphs with an application to optical networks ⋮ Truthful facility assignment with resource augmentation: an exact analysis of serial dictatorship ⋮ Near optimal algorithms for online maximum edge-weighted \(b\)-matching and two-sided vertex-weighted \(b\)-matching ⋮ Truthful Facility Assignment with Resource Augmentation: An Exact Analysis of Serial Dictatorship ⋮ Online Matching in Regular Bipartite Graphs with Randomized Adversary ⋮ Improved bounds for randomized preemptive online matching ⋮ Online bottleneck matching ⋮ Unnamed Item ⋮ Randomized algorithms for the on-line minimum matching problem on euclidean space ⋮ A randomized \(O(\log^2k)\)-competitive algorithm for metric bipartite matching ⋮ Dynamic pricing of servers on trees ⋮ Permutation Strikes Back: The Power of Recourse in Online Metric Matching ⋮ When LP is the cure for your matching woes: improved bounds for stochastic matchings ⋮ Two online algorithms for the ambulance systems ⋮ Unnamed Item ⋮ Deterministic min-cost matching with delays ⋮ Online facility assignment ⋮ Pricing and allocation algorithm designs in dynamic ridesharing system ⋮ 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 ⋮ On-Line Maximum Matching in Complete Multipartite Graphs with Implications to the Minimum ADM Problem on a Star Topology ⋮ An optimal deterministic algorithm for online \(b\)-matching ⋮ Maximum matching on trees in the online preemptive and the incremental graph models ⋮ The fast algorithm for online \(k\)-server problem on trees ⋮ Some recent results in the analysis of greedy algorithms for assignment problems ⋮ Competitive strategies for an online generalized assignment problem with a service consecution constraint
This page was built for publication: Online Weighted Matching
