Permutation Strikes Back: The Power of Recourse in Online Metric Matching

DOI10.4230/LIPICS.APPROX/RANDOM.2020.40MaRDI QIDQ6084396zbMATH OpenOpenAlexFDO

Authors

Publication date 31 October 2023

Full work available at URL https://arxiv.org/abs/1911.12778

zbMATH Keywords

bipartite matchingonline algorithms

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Online algorithms; streaming algorithms (68W27) Analysis of algorithms (68W40) Combinatorial optimization (90C27)

Abstract: In the classical Online Metric Matching problem, we are given a metric space with $k$ servers. A collection of clients arrive in an online fashion, and upon arrival, a client should irrevocably be matched to an as-yet-unmatched server. The goal is to find an online matching which minimizes the total cost, i.e., the sum of distances between each client and the server it is matched to. We know deterministic algorithms~cite{KP93,khuller1994line} that achieve a competitive ratio of $2k-1$, and this bound is tight for deterministic algorithms. The problem has also long been considered in specialized metrics such as the line metric or metrics of bounded doubling dimension, with the current best result on a line metric being a deterministic $O(logk)$ competitive algorithm~cite{raghvendra2018optimal}. Obtaining (or refuting) $O(logk)$-competitive algorithms in general metrics and constant-competitive algorithms on the line metric have been long-standing open questions in this area. In this paper, we investigate the robustness of these lower bounds by considering the Online Metric Matching with Recourse problem where we are allowed to change a small number of previous assignments upon arrival of a new client. Indeed, we show that a small logarithmic amount of recourse can significantly improve the quality of matchings we can maintain. For general metrics, we show a simple emph{deterministic} $O(logk)$-competitive algorithm with $O(logk)$-amortized recourse, an exponential improvement over the $2k-1$ lower bound when no recourse is allowed. We next consider the line metric, and present a deterministic algorithm which is $3$-competitive and has $O(logk)$-recourse, again a substantial improvement over the best known $O(logk)$-competitive algorithm when no recourse is allowed.

Recommendations

• Online maximum matching with recourse
• Online maximum matching with recourse
• A randomized O(^2k)-competitive algorithm for metric bipartite matching
• An O(log2 k)-Competitive Algorithm for Metric Bipartite Matching
• Stochastic online metric matching

Cites work

• A collection of lower bounds for online matching on the line
• A match in time saves nine: deterministic online matching with delays
• An O(log2 k)-Competitive Algorithm for Metric Bipartite Matching
• Approximation and Online Algorithms
• Fully-dynamic bin packing with little repacking
• scientific article; zbMATH DE number 5764830 (Why is no real title available?)
• Maintaining assignments online: matching, scheduling, and flows
• Maintaining perfect matchings at low cost
• New algorithms, better bounds, and a novel model for online stochastic matching
• On-line algorithms for weighted bipartite matching and stable marriages
• Online and dynamic algorithms for set cover
• Online matching on a line
• Online matching: haste makes waste!
• Online Weighted Matching
• Randomized online algorithms for minimum metric bipartite matching
• Stochastic online metric matching
• The Online Metric Matching Problem for Doubling Metrics

Cited in

(12)

• Online load balancing with general reassignment cost
• The Online Metric Matching Problem for Doubling Metrics
• Online maximum matching with recourse
• The power of recourse for online MST and TSP
• Matching on the Line Admits no \(o(\sqrt {\log n})\) -Competitive Algorithm
• Interval-constrained bipartite matching over time
• Online deterministic minimum cost bipartite matching with delays on a line
• Adaptive-adversary-robust algorithms via small copy tree embeddings
• Online metric matching on the line with recourse
• Matching on the line admits no \(o(\sqrt{\log n})\)-competitive algorithm
• Interval-constrained bipartite matching over time
• Online maximum matching with recourse

This page was built for publication: Permutation Strikes Back: The Power of Recourse in Online Metric Matching

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