A new rounding procedure for the assignment problem with applications to dense graph arrangement problems
Authors:
- S. AroraSAS. Arora
- A. FriezeAFA. Frieze
- H. KaplanHKH. Kaplan
- 24 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 92 (1) , 21-30
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 εn2 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.Keywords
This publication has 15 references indexed in Scilit:
- The regularity lemma and approximation schemes for dense problems2002
- Towards a syntactic characterization of PTAS1996
- The quadratic assignment problem: A survey and recent developments1994
- Approximation algorithms for NP-complete problems on planar graphsJournal of the ACM, 1994
- A parallel approximation algorithm for positive linear programming1993
- An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms1988
- Randomized rounding: A technique for provably good algorithms and algorithmic proofsCombinatorica, 1987
- A fast parallel algorithm for routing in permutation networksIEEE Transactions on Computers, 1981
- P-Complete Approximation ProblemsJournal of the ACM, 1976
- Fast Approximation Algorithms for the Knapsack and Sum of Subset ProblemsJournal of the ACM, 1975