TY - JOUR

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

AU - Arora, Sanjeev

AU - Frieze, Alan

AU - Kaplan, Haim

PY - 1996/12/1

Y1 - 1996/12/1

N2 - 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. It also solves an open problem of Luby and Nisan (`Design an NC procedure for converting near-optimum fractional matchings to near-optimum matchings.') We use the rounding procedure to design nO(log n/ε(2)) time algorithms for the following: (i) an additive approximation to the 0 - 1 Quadratic Assignment Problem (QAP). (ii) a (1+ε)-approximation for `dense' instances of many well-known NP-hard problems, including (an optimization formulation of) GRAPH-ISOMORPHISM, MIN-CUT-LINEAR-ARRANGEMENT, MAX-ACYCLIC-SUBGRAPH, MIN-LINEAR-ARRANGEMENT, and BETWEENNESS. (A `dense' graph is one in which the number of edges is Ω(n2); denseness for the other problems is defined in an analogous way.)

AB - 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. It also solves an open problem of Luby and Nisan (`Design an NC procedure for converting near-optimum fractional matchings to near-optimum matchings.') We use the rounding procedure to design nO(log n/ε(2)) time algorithms for the following: (i) an additive approximation to the 0 - 1 Quadratic Assignment Problem (QAP). (ii) a (1+ε)-approximation for `dense' instances of many well-known NP-hard problems, including (an optimization formulation of) GRAPH-ISOMORPHISM, MIN-CUT-LINEAR-ARRANGEMENT, MAX-ACYCLIC-SUBGRAPH, MIN-LINEAR-ARRANGEMENT, and BETWEENNESS. (A `dense' graph is one in which the number of edges is Ω(n2); denseness for the other problems is defined in an analogous way.)

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

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

M3 - Article

AN - SCOPUS:0030409562

SN - 0272-5428

SP - 21

EP - 30

JO - Annual Symposium on Foundations of Computer Science - Proceedings

JF - Annual Symposium on Foundations of Computer Science - Proceedings

ER -