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

Sanjeev Arora, Alan Frieze, Haim Kaplan

Research output: Contribution to journalArticle

43 Scopus citations

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. 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.)

Original languageEnglish (US)
Pages (from-to)21-30
Number of pages10
JournalAnnual Symposium on Foundations of Computer Science - Proceedings
StatePublished - Dec 1 1996

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'New rounding procedure for the assignment problem with applications to dense graph arrangement problems'. Together they form a unique fingerprint.

  • Cite this