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