arXiv preprint ·
Approximation Algorithm for the Min-Cost Bipartite Matching with Penalties
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Geometry
$c$-Packedness versus $λ$-Low-Density in Geometric Graphs: Theory and Practice
Fast Geometric Spanners via Approximate Nearest Neighbor Search
Homological Trimming and Regularity of Filtrations via Local Obstruction Modules
Positive Pair Geometry Matters: Optimal Transport for Contrastive Learning of Visual Representations
WildHSR: Metric Feed-Forward 4D People-Scene Reconstruction from a 3D Foundation Model
Get the few papers worth your time in Computational Geometry every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.