caa a22 4500 467909709 CHVBK 20180406152846.0 cr unu---uuuuu 170328e20060601xx s 000 0 eng 10.1007/s00037-006-0210-9 doi (NATIONALLICENCE)springer-10.1007/s00037-006-0210-9 ON THE HARDNESS OF APPROXIMATING MULTICUT AND SPARSEST-CUT [Elektronische Daten] [Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, D. Sivakumar] 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 (2002). A quantitatively stronger version of the conjecture implies an inapproximability factor of $$\Omega(\sqrt{\log \log n}).$$ Birkhäuser Verlag, Basel, 2006 Multicut nationallicence sparsest-cut nationallicence unique games conjecture nationallicence Fourier analysis nationallicence 68Q17 nationallicence Chawla Shuchi Computer Science Department, Carnegie Mellon University, 15213, Pittsburgh, PA, U.S.A aut Krauthgamer Robert IBM Almaden Research Center, 650 Harry Road, 95120, San Jose, CA, U.S.A aut Kumar Ravi IBM Almaden Research Center, 650 Harry Road, 95120, San Jose, CA, U.S.A aut Rabani Yuval Computer Science Department, Technion—Israel Institute of Technology, 32000, Haifa, Israel aut Sivakumar D. IBM Almaden Research Center, 650 Harry Road, 95120, San Jose, CA, U.S.A aut computational complexity Birkhäuser-Verlag; www.birkhauser.ch 15/2(2006-06-01), 94-114 1016-3328 15:2<94 2006 15 37 https://doi.org/10.1007/s00037-006-0210-9 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00037-006-0210-9 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Chawla Shuchi Computer Science Department, Carnegie Mellon University, 15213, Pittsburgh, PA, U.S.A aut NATIONALLICENCE 700 1- Krauthgamer Robert IBM Almaden Research Center, 650 Harry Road, 95120, San Jose, CA, U.S.A aut NATIONALLICENCE 700 1- Kumar Ravi IBM Almaden Research Center, 650 Harry Road, 95120, San Jose, CA, U.S.A aut NATIONALLICENCE 700 1- Rabani Yuval Computer Science Department, Technion—Israel Institute of Technology, 32000, Haifa, Israel aut NATIONALLICENCE 700 1- Sivakumar D. IBM Almaden Research Center, 650 Harry Road, 95120, San Jose, CA, U.S.A aut NATIONALLICENCE 773 0- computational complexity Birkhäuser-Verlag; www.birkhauser.ch 15/2(2006-06-01), 94-114 1016-3328 15:2<94 2006 15 37 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer