A Deterministic Polylogarithmic Competitive Algorithm for Matching with Delays
Abstract
In the online Min-cost Perfect Matching with Delays (\(\textsf{MPMD}\)) problem, \(m\) requests in a metric space are submitted at different times by an adversary. The goal is to match all requests while (i) minimizing the sum of the distances between matched pairs as well as (ii) how long each request remained unmatched after it appeared.
Fields of Study & Subjects
Optimization and Search Problems
Distributed systems and fault tolerance
Advanced Bandit Algorithms Research
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 3936–3964
- Publication date
- 1 January 2026
- Language
- EN