Stability vs. Cost of Matchings

Details Stability vs. Cost of Matchings Stability vs. Cost of Matchings

2011-12-20

arxiv.org/abs/1112.4632v3

Computer Science

Computational Geometry

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Stability vs. Cost of Matchings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Stability vs. Cost of Matchings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Stability vs. Cost of Matchings will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-56030