On the Hardness of Approximating Multicut and Sparsest-Cut

Authors:
  • RKR. Krauthgamer
    R. Krauthgamer
  • RKR. Kumar
    R. Kumar
  • YRY. Rabani
    Y. Rabani
  • DSD. Sivakumar
    D. Sivakumar

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

This publication has 19 references indexed in Scilit: