A new rounding procedure for the assignment problem with applications to dense graph arrangement problems |
| |
| Authors: | Sanjeev Arora Alan Frieze Haim Kaplan |
| |
| Institution: | (1) Computer Science, Princeton University, e-mail: arora@cs.princeton.edu, US;(2) Department of Mathematics, Carnegie Mellon University, Pittsburgh PA15213, e-mail: alan@random.math.cmu.edu, US;(3) Department of Computer Science, Tel-Aviv University, Tel-Aviv 69978, Israel, e-mail: haimk@math.tau.ac.il, US |
| |
| Abstract: | We present a randomized procedure for rounding fractional perfect matchings to (integral) matchings. If the original fractional
matching satisfies any linear inequality, then with high probability, the new matching satisfies that linear inequality in
an approximate sense. This extends the well-known LP rounding procedure of Raghavan and Thompson, which is usually used to
round fractional solutions of linear programs.?We use our rounding procedure to design an additive approximation algorithm
to the Quadratic Assignment Problem. The approximation error of the algorithm is εn
2 and it runs in n
O
(log
n
/ε2) time.?We also describe Polynomial Time Approximation Schemes (PTASs) for dense subcases of many well-known NP-hard arrangement
problems, including MINIMUM LINEAR ARRANGEMENT, MINIMUM CUT LINEAR ARRANGEMENT, MAXIMUM ACYCLIC SUBGRAPH, and BETWEENNESS.
Received: December 12, 1999 / Accepted: October 25, 2001?Published online February 14, 2002 |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
