Title :
On the hardness of approximating MULTICUT and SPARSEST-CUT
Author :
Chawla, Shuchi ; Krauthgamer, Robert ; Kumar, Ravi ; Rabani, Yuval ; Sivakumar, D.
Author_Institution :
Dept. of Comput. Sci., Carnegie Mellon Univ., Pittsburgh, PA, USA
Abstract :
We show that the MULTICUT, SPARSEST-CUT, and MIN-2CNF≡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 Ω(log log n).
Keywords :
approximation theory; computational complexity; game theory; graph theory; MIN-2CNF≡DELETION problem; MULTICUT problem; NP-hard problem; SPARSEST-CUT problem; approximation hardness; multicut approximation; sparsest-cut approximation; unique games; Approximation algorithms; Computer science; Costs; Linear programming; Mathematics;
Conference_Titel :
Computational Complexity, 2005. Proceedings. Twentieth Annual IEEE Conference on
Print_ISBN :
0-7695-2364-1
DOI :
10.1109/CCC.2005.20
