DocumentCode :
2074660
Title :
O(√log n) approximation to SPARSEST CUT in O˜(n2) time
Author :
Arora, Sanjeev ; Hazan, Elad ; Kale, Satyen
Author_Institution :
Dept. of Comput. Sci., Princeton Univ., NJ, USA
fYear :
2004
fDate :
17-19 Oct. 2004
Firstpage :
238
Lastpage :
247
Abstract :
We show how to compute O(√log n)-approximations to SPARSEST CUT and BALANCED SEPARATOR problems in O˜(n2) time, thus improving upon the recent algorithm of Arora, Rao and Vazirani (2004). Their algorithm uses semidefinite programming and required O˜(n4.5) time. Our algorithm relies on efficiently finding expander flows in the graph and does not solve semidefinite programs. The existence of expander flows was also established by Arora, Rao, and Vazirani.
Keywords :
computational complexity; graph theory; BALANCED SEPARATOR problem; O(√log n) approximation; O(n2) time; SPARSEST CUT; expander flow; graph theory; semidefinite programming; Algorithm design and analysis; Approximation algorithms; Clustering algorithms; Computer science; Graph theory; NP-hard problem; Particle separators; Partitioning algorithms; Phase change random access memory; Routing;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on
ISSN :
0272-5428
Print_ISBN :
0-7695-2228-9
Type :
conf
DOI :
10.1109/FOCS.2004.1
Filename :
1366243
Link To Document :
https://search.ricest.ac.ir/dl/search/defaultta.aspx?DTC=49&DC=2074660
بازگشت