TY - JOUR

T1 - A new rounding procedure for the assignment problem with applications to dense graph arrangement problems

AU - Arora, Sanjeev

AU - Frieze, Alan

AU - Kaplan, Haim

PY - 2002/3

Y1 - 2002/3

N2 - We present a randomized procedure for founding 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 ∈ 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.

AB - We present a randomized procedure for founding 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 ∈ 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.

UR - http://www.scopus.com/inward/record.url?scp=3142748958&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=3142748958&partnerID=8YFLogxK

U2 - https://doi.org/10.1007/s101070100271

DO - https://doi.org/10.1007/s101070100271

M3 - Article

SN - 0025-5610

VL - 92

SP - 1

EP - 36

JO - Mathematical Programming, Series B

JF - Mathematical Programming, Series B

IS - 1

ER -