The problem of min-cost matching with delays is an online problem defined on an underlyingn-point metric space as follows. An adversary presents real-time requests online at points of the metric space, and the algorithm is required to match them, possibly after keeping them waiting for some time. The cost incurred is the sum of the distances between matched pairs of requests (the connection cost), and the sum of the waiting times of the requests (the delay cost). This objective exhibits a natural trade-off between minimizing the distances and the cost of waiting for better matches. The problem comes in two flavors: the non-bipartite one (MPMD) and the bipartite one (MBPMD). In the non-bipartite version, any two requests can be matched, while on the other hand, in the bipartite version, each request is either positive or negative, and two requests may be matched only if they have opposite polarities.   

The problem of non-bipartite min-cost matching with delays was recently introduced by Emek et al. For an n-point metric space in which the largest distance is ∆ times the smallest, Emek et al. give an algorithm with a competitive ratio O((log n)^2 + log ∆). We present an improved algorithm with a competitive ratio of O(log n), removing the dependence on ∆. We also prove a lower bound of O(log n/loglog n) on the competitive ratio of any randomized algorithm, almost matching the upper bound. For bipartite min-cost matching with delays, we give an O(log n)-competitive algorithm, and prove a lower bound of O(/sqrt(log n/loglog n)).

The core of our algorithms for MPMD and MBPMD are deterministic algorithms for the respective problems on metrics induced by edge-weighted trees of height h. The algorithms' cost is guaranteed to be at most O(1) times the connection cost plus O(h) times the delay cost of every feasible solution. The reduction from M(B)PMD on arbitrary metrics to M(B)PMD on tree metrics is achieved using the result on embedding n-point metric spaces into distributions over weighted hierarchically separated trees of height O(log n), with distortion O(log n). Both of our lower bounds are attained on the metric space of n equally spaced points on a line.

海报