Metadata only

Author

Emek, Yuval

Langner, Tobias

Wattenhofer, Roger

Date

2011-12Type

- Working Paper

ETH Bibliography

yes
Altmetrics

Abstract

This paper studies the classic minimum-cost perfect matching problem in complete graphs under certain stability constraints. Given some real $\alpha \geq 1$, a matching $M$ is said to be \emph{$\alpha$-stable} if there does not exist any edge $(x, y) \notin M$ such that $\alpha \cdot w(x, y) < \min\{ w(x, x'), w(y, y') \}$, where $x'$ and $y'$ are the vertices matched to $x$ and $y$, respectively, under $M$. Given some real $\beta \geq 1$, the perfect matching $M$ is said to be \emph{$\beta$-minimum} if the total cost of $M$ is at most $\beta$ times larger than that of the minimum-cost perfect matching. We present a simple greedy algorithm that transforms a minimum-cost perfect matching on $2 n$ vertices into an $\alpha$-stable and $\beta$-minimum matching where $\beta = \BigO(n^{\log(1 + 1 / (2 \alpha))})$. In particular, this means that we can obtain a constant approximation for the minimum-cost perfect matching by choosing $\alpha = \BigO(\log n)$. On the negative side, we show that for any $\alpha \geq 1$, there exists a metric graph such that no $\alpha$-stable perfect matching can be $\beta$-minimum unless $\beta = \Omega(n^{\log(1 + 1 / (2 \alpha))})$. Together, our findings establish an asymptotically tight trade-off between the (local) stability and the (global) cost of perfect matchings Show more

Publication status

publishedPages / Article No.

Publisher

Cornell UniversityOrganisational unit

03604 - Wattenhofer, Roger / Wattenhofer, Roger
Notes

Submitted on 20 Dec 2011 (v1), Last revised 19 Jan 2012 (this version, v3).More

Show all metadata
ETH Bibliography

yes
Altmetrics