SCIENCE@home

Online matching: haste makes waste!

Y. Emek,S. Kutten,Roger Wattenhofer

Published 2016 in Symposium on the Theory of Computing

ABSTRACT

This paper studies a new online problem, referred to as 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) M that is known to the algorithm in advance. Requests arrive in a continuous time online fashion at the points of M 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 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 O (log2 n + logΔ), where n is the number of points in M 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.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-39 of 39 references · Page 1 of 1

CITED BY

Showing 1-81 of 81 citing papers · Page 1 of 1