Permutation Strikes Back: The Power of Recourse in Online Metric Matching
From MaRDI portal
Publication:6084396
DOI10.4230/LIPICS.APPROX/RANDOM.2020.40zbMath1523.68175arXiv1911.12778OpenAlexW3081862881MaRDI QIDQ6084396
No author found.
Publication date: 31 October 2023
Full work available at URL: https://arxiv.org/abs/1911.12778
Analysis of algorithms (68W40) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Online algorithms; streaming algorithms (68W27)
Related Items (2)
Online load balancing with general reassignment cost ⋮ Matching on the Line Admits no \(o(\sqrt {\log n})\) -Competitive Algorithm
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On-line algorithms for weighted bipartite matching and stable marriages
- A match in time saves nine: deterministic online matching with delays
- Online matching on a line
- A collection of lower bounds for online matching on the line
- The Online Metric Matching Problem for Doubling Metrics
- An O(log2 k)-Competitive Algorithm for Metric Bipartite Matching
- Randomized online algorithms for minimum metric bipartite matching
- Online Weighted Matching
- Online and dynamic algorithms for set cover
- Fully-Dynamic Bin Packing with Little Repacking
- Stochastic Online Metric Matching
- Online matching: haste makes waste!
- Maintaining Assignments Online: Matching, Scheduling, and Flows
- Approximation and Online Algorithms
- Deterministic min-cost matching with delays
This page was built for publication: Permutation Strikes Back: The Power of Recourse in Online Metric Matching
