Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Point processes (e.g., Poisson, Cox, Hawkes processes) (60G55) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)
Abstract: This paper studies a new online problem, referred to as emph{min-cost perfect matching with delays (MPMD)}, defined over a finite metric space (i.e., a complete graph with positive edge weights obeying the triangle inequality) that is known to the algorithm in advance. Requests arrive in a continuous time online fashion at the points of and should be served by matching them to each other. The algorithm is allowed to delay its request matching commitments, but this does not come for free: the total cost of the algorithm is the sum of metric distances between matched requests emph{plus} the sum of times each request waited since it arrived until it was matched. A randomized online MPMD algorithm is presented whose competitive ratio is , where is the number of points in and is its aspect ratio. The analysis is based on a machinery developed in the context of a new stochastic process that can be viewed as two interleaved Poisson processes; surprisingly, this new process captures precisely the behavior of our algorithm. A related problem in which the algorithm is allowed to clear any unmatched request at a fixed penalty is also addressed. It is suggested that the MPMD problem is merely the tip of the iceberg for a general framework of online problems with delayed service that captures many more natural problems.
Recommendations
Cited in
(31)- Minimum cost perfect matching with delays for two sources
- A match in time saves nine: deterministic online matching with delays
- A primal-dual online deterministic algorithm for matching with delays
- Stable secretaries
- On bin packing with clustering and bin packing with delays
- Online service with delay
- Competitive analysis for two variants of online metric matching problem
- Online service with delay
- Online perfect matching and mobile computing
- Asymptotically Optimal Control of a Centralized Dynamic Matching Market with General Utilities
- Impatient Online Matching
- Caching with time windows and delays
- Technical note -- Online hypergraph matching with delays
- Minimum cost perfect matching with delays for two sources
- scientific article; zbMATH DE number 7651147 (Why is no real title available?)
- The k-Server Problem with Delays on the Uniform Metric Space
- Permutation Strikes Back: The Power of Recourse in Online Metric Matching
- Distributed maximum matching verification in CONGEST
- Quick or cheap? Breaking points in dynamic markets
- Deterministic primal-dual algorithms for online k-way matching with delays
- Randomized algorithm for MPMD on two sources
- Deterministic primal-dual algorithms for online \(k\)-way matching with delays
- List update with delays or time windows
- Universal optimization for non-clairvoyant subadditive joint replenishment
- Online deterministic minimum cost bipartite matching with delays on a line
- MPMD on two sources with lookahead
- 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
- Title not available (Why is no real title available?)
- Title not available (Why is no real title available?)
This page was built for publication: Online matching: haste makes waste!
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5361841)
