On the Hardness of Approximating Multicut and Sparsest-Cut
Authors:
- R. KrauthgamerRKR. Krauthgamer
- R. KumarRKR. Kumar
- Y. RabaniYRY. Rabani
- D. SivakumarDSD. Sivakumar
- 28 June 2005
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 144-153
Abstract
We show that the MULTICUT, SPARSEST-CUT, and MIN-2CNF/spl equiv/DELETION problems are NP-hard to approximate within every constant factor, assuming the unique games conjecture of Khot [STOC, 2002]. A quantitatively stronger version of the conjecture implies inapproximability factor of /spl Omega/(log log n).Keywords
This publication has 19 references indexed in Scilit:
- Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs?2004
- Vertex cover might be hard to approximate to within 2-ε2004
- On Systems of Linear Equations with Two Variables per EquationLecture Notes in Computer Science, 2004
- On the power of unique 2-prover 1-round games2003
- Approximation through multicommodity flow2002
- Some optimal inapproximability resultsJournal of the ACM, 2001
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their ApplicationsSIAM Journal on Computing, 1996
- The Complexity of Multiterminal CutsSIAM Journal on Computing, 1994
- The influence of variables on Boolean functions1988
- An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms1988