Approximate fast matching algorithm balances cost and penalties
Approximation Algorithm for the Min-Cost Bipartite Matching with Penalties
Computational GeometryData Structures and Algorithms
Summary
Matching pairs from two groups to minimize travel cost can be tricky when some points are allowed to remain unmatched with a penalty. The authors study this problem in special spaces where distances have a certain structure. They designed a fast randomized method that nearly finds the best way to pair points while also deciding which points to leave unmatched with penalties. This is the first near-linear time efficient solution for this matching problem with penalties in such spaces.
What this means in practice
- •For logistics planners: Optimize pairing of supply and demand locations quickly when some sites can remain unserved at a cost.
- •For network schedulers: Schedule task assignments between two types of resources allowing penalties for skipped tasks in near-real time.
Authors
Eunjin Oh, Seongbin Park, Chanho Song
Abstract
In this paper, we study the minimum-cost bipartite matching with penalties problem in metric spaces with bounded doubling dimension: Given two disjoint sets $R, B$ in a metric space $\mathcal{M}$ with $|R|+|B|=n$ and a penalty function $p \colon R \cup B \to \mathbb{R}_{\ge 0}$, the goal is to select a set of pairs in $R\times B$ so that every point belongs to at most one pair and the sum of the distances of the selected pairs and the penalties of the points not belonging to any pair is minimized. While near-linear time approximation algorithms are known for the minimum-cost perfect matching problem in geometric settings, no such algorithm was previously known for the penalty setting. We present a randomized algorithm that computes a $(1+\varepsilon)$-approximate minimum-cost bipartite matching with penalties in $O(n \mathrm{poly}(\log n, 1/\varepsilon))$ time with high probability. To the best of our knowledge, this is the first near-linear time approximation algorithm for the problem in the penalty setting.