loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
20th Annual IEEE Conference on Computational Complexity (CCC'05)
On the Hardness of Approximating Multicut and Sparsest-Cut
San Jose, CA
June 11-June 15
ISBN: 0-7695-2364-1
ASCII Text
x 
 
Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, D. Sivakumar, "On the Hardness of Approximating Multicut and Sparsest-Cut," Computational Complexity, Annual IEEE Conference on, pp. 144-153, 20th Annual IEEE Conference on Computational Complexity (CCC'05), 2005.
 
 
BibTex
x
 
@article{ 10.1109/CCC.2005.20,
author = {Shuchi Chawla and Robert Krauthgamer and Ravi Kumar and Yuval Rabani and D. Sivakumar},
title = {On the Hardness of Approximating Multicut and Sparsest-Cut},
journal ={Computational Complexity, Annual IEEE Conference on},
volume = {0},
year = {2005},
issn = {1093-0159},
pages = {144-153},
doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2005.20},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Computational Complexity, Annual IEEE Conference on
TI - On the Hardness of Approximating Multicut and Sparsest-Cut
SN - 1093-0159
SP144
EP153
A1 - Shuchi Chawla,
A1 - Robert Krauthgamer,
A1 - Ravi Kumar,
A1 - Yuval Rabani,
A1 - D. Sivakumar,
PY - 2005
KW - null
VL - 0
JA - Computational Complexity, Annual IEEE Conference on
ER -
 
Shuchi Chawla, Carnegie Mellon University
Robert Krauthgamer, IBM Almaden Research Center
Ravi Kumar, IBM Almaden Research Center
Yuval Rabani, Technion-Israel Institute of Technology, Cornell University, IBM Almaden Research Center and University of California at Los Angeles
D. Sivakumar, IBM Almaden Research Center
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).
Citation:
Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, D. Sivakumar, "On the Hardness of Approximating Multicut and Sparsest-Cut," ccc, pp.144-153, 20th Annual IEEE Conference on Computational Complexity (CCC'05), 2005
Usage of this product signifies your acceptance of the Terms of Use.