Online Minimum Cost Matching on the Line with Recourse
Preprint
Abstract
In online minimum cost matching on the line, $n$ requests appear one by one and have to be matched immediately and irrevocably to a given set of servers, all on the real line. The goal is to minimize the sum of distances from the requests to their respective servers. Despite all research efforts, it remains an intriguing open question whether there exists an $O(1)$-competitive algorithm. The best known online algorithm by Raghvendra [SoCG18] achieves a competitive factor of $\Theta(\log n)$. This result matches a lower bound of $\Omega(\log n)$ [Latin18] that holds for a quite large class of online algorithms, including all deterministic algorithms in the literature. In this work we approach the problem in a recourse model where we allow to revoke online decisions to some extent. We show an $O(1)$-competitive algorithm for online matching on the line that uses at most $O(n\log n)$ reassignments. This is the first non-trivial result for min-cost bipartite matching with recourse. For so-called alternating instances, with no more than one request between two servers, we obtain a near-optimal result. We give a $(1+\varepsilon)$-competitive algorithm that reassigns any request at most $O(\varepsilon^{-1.001})$ times. This special case is interesting as the aforementioned quite general lower bound $\Omega(\log n)$ holds for such instances.
Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Online maximum matching with recourseJournal of Combinatorial Optimization, 2020
- Greedy metric minimum online matchings with random arrivalsOperations Research Letters, 2019
- An Input Sensitive Online Algorithm for the Metric Bipartite Matching Problem2017
- A $o(n)$-Competitive Deterministic Algorithm for Online Matching on a Line2015
- A Randomized O(log2 k)-Competitive Algorithm for Metric Bipartite MatchingAlgorithmica, 2012
- The Online Metric Matching Problem for Doubling Metrics2012
- Online matching on a lineTheoretical Computer Science, 2005
- On-line algorithms for weighted bipartite matching and stable marriagesTheoretical Computer Science, 1994
- Online Weighted MatchingJournal of Algorithms, 1993
- Dynamic Steiner Tree ProblemSIAM Journal on Discrete Mathematics, 1991