Journal
COMPUTATIONAL COMPLEXITY
Volume 15, Issue 2, Pages 94-114Publisher
SPRINGER BASEL AG
DOI: 10.1007/s00037-006-0210-9
Keywords
multicut; sparsest-cut; unique games conjecture; Fourier analysis
Categories
Ask authors/readers for more resources
We show that the MULTICUT, SPARSEST-CUT, and MIN2CNF equivalent to DELETION problems are NP-hard to approximate within every constant factor, assuming the Unique Games Conjecture of Khot (2002). A quantitatively stronger version of the conjecture implies an inapproximability factor of Omega (root log log n).
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available
Share Paper
