Approximation Algorithm for the Min-Cost Bipartite Matching with Penalties

Eunjin Oh; Seongbin Park; Chanho Song

In the authors' words

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 $M$ with $∣ R ∣ + ∣ B ∣ = n$ and a penalty function $p : R \cup B \to R_{\geq 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 + ε)$ -approximate minimum-cost bipartite matching with penalties in $O (n p o l y (lo g n, 1/ ε))$ 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.

Main resultThe abstract does not state a limitation.

Approximation Algorithm for the Min-Cost Bipartite Matching with Penalties

In the authors' words

More on Algorithms & complexity that day

4-Block Integer Programming is in FPT

An Approximation Algorithm for Non-uniform Non-contiguous Translocation Distance

Analysis of trade-offs in urban heat mitigation using a Bayesian Optimization framework for an urban canopy layer model

Factorisability of Low Dimensional Non-Negative Integer Matrices

An Exponential Succinctness Gap between Three-Variable Logic and the Calculus of Relations