A Deterministic Polylogarithmic Competitive Algorithm for Matching with Delays

Marc Dufay, Roger Wattenhofer

In the online Min-cost Perfect Matching with Delays (MPMD) problem, $m$ requests in a metric space are submitted at different times by an adversary. The goal is to match all reques…