A match in time saves nine: deterministic online matching with delays

DOI10.1007/978-3-319-89441-6_11MaRDI QIDQ1644933zbMATH OpenOpenAlexFDO

Authors Marcin Bienkowski, Artur Kraska, Paweł Schmidt

Publication date 22 June 2018

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

zbMATH Keywords

competitive analysisdelaysonline matchingrent-or-buy

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27)

Abstract: We consider the problem of online Min-cost Perfect Matching with Delays (MPMD) introduced by Emek et al. (STOC 2016). In this problem, an even number of requests appear in a metric space at different times and the goal of an online algorithm is to match them in pairs. In contrast to traditional online matching problems, in MPMD all requests appear online and an algorithm can match any pair of requests, but such decision may be delayed (e.g., to find a better match). The cost is the sum of matching distances and the introduced delays. We present the first deterministic online algorithm for this problem. Its competitive ratio is $O(m^{lo{g}_{2}5.5})$ $=O(m^{2.46})$, where $2m$ is the number of requests. This is polynomial in the number of metric space points if all requests are given at different points. In particular, the bound does not depend on other parameters of the metric, such as its aspect ratio. Unlike previous (randomized) solutions for the MPMD problem, our algorithm does not need to know the metric space in advance.

Recommendations

• A primal-dual online deterministic algorithm for matching with delays
• Online matching: haste makes waste!
• Minimum cost perfect matching with delays for two sources

Cited in

(18)

• A primal-dual online deterministic algorithm for matching with delays
• On bin packing with clustering and bin packing with delays
• Competitive analysis for two variants of online metric matching problem
• Impatient Online Matching
• Minimum cost perfect matching with delays for two sources
• Online matching: haste makes waste!
• scientific article; zbMATH DE number 7651147 (Why is no real title available?)
• Permutation Strikes Back: The Power of Recourse in Online Metric Matching
• Deterministic primal-dual algorithms for online k-way matching with delays
• Capacity-insensitive algorithms for online facility assignment problems on a line
• Deterministic primal-dual algorithms for online \(k\)-way matching with delays
• Universal optimization for non-clairvoyant subadditive joint replenishment
• Online deterministic minimum cost bipartite matching with delays on a line
• Online deterministic minimum cost bipartite matching with delays on a line
• Online matching with delays and stochastic arrival times
• Universal optimization for non-clairvoyant subadditive joint replenishment
• Online multi-level aggregation with delays and stochastic arrivals
• Nearly-optimal algorithm for non-clairvoyant service with delay

This page was built for publication: A match in time saves nine: deterministic online matching with delays

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