Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(7)
Approximate Algorithm
Conduct Problems
Graph Partitioning
multicommodity flow
semidefinite program
semidefinite relaxation
Triangle Inequality
Subscribe
Academic
Publications
Expander flows, geometric embeddings and graph partitioning
Expander flows, geometric embeddings and graph partitioning,10.1145/1502793.1502794,Journal of The ACM,Sanjeev Arora,Satish Rao,Umesh V. Vazirani
Edit
Expander flows, geometric embeddings and graph partitioning
(
Citations: 20
)
BibTex

RIS

RefWorks
Download
Sanjeev Arora
,
Satish Rao
,
Umesh V. Vazirani
We give a O(&sqrt;log n)approximation algorithm for the sparsest cut, edge expansion, balanced separator, and graph conductance problems. This improves the O(log n)approximation of Leighton and Rao (1988). We use a wellknown
semidefinite relaxation
with
triangle inequality
constraints. Central to our analysis is a geometric theorem about projections of point sets in Rd, whose proof makes essential use of a phenomenon called measure concentration. We also describe an interesting and natural “approximate certificate” for a graph's expansion, which involves embedding an nnode expander in it with appropriate dilation and congestion. We call this an expander flow.
Journal:
Journal of The ACM  JACM
, vol. 56, no. 2, pp. 137, 2009
DOI:
10.1145/1502793.1502794
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
portal.acm.org
)
(
portal.acm.org
)
(
doi.acm.org
)
(
www.informatik.unitrier.de
)
(
portal.acm.org
)
More »
Citation Context
(9)
...The best known polynomial algorithm for the crossing number of general graphs with bounded degree [
1
, 12] approximates, within a factor of log 2 V (G), the quantity V (G) +c r( G), not directly cr(G)...
Markus Chimani Petr Hlineny
,
et al.
A Tighter Insertionbased Approximation of the Crossing Number
...The MCP is a NPhard problem, and there exist a rich suite of both theoretical and practical algorithms to optimize the conductance quantity [
20
], [21]...
Qing Ke
,
et al.
Efficient Search in Networks Using Conductance
...For example, two rounds of Lasserre applied to the MaxCut LP yields an SDP that is at least as strong as that used by Goemans and Williamson to get the best known approximation algorithm, and the SDP in [
3
] which leads to the best known approximation algorithm for SparsestCut can be obtained by three rounds of Lasserre...
Anna R. Karlin
,
et al.
Integrality Gaps of Linear and Semidefinite Programming Relaxations f...
...If one uses O( p logn)approximate sparsest cuts [
3
, 2, 20],...
Ran Duan
,
et al.
Connectivity oracles for failure prone graphs
...arbitrary O( √ log n )S DP [
3
] excluding fixedminor O(1) LP (flow) [24, 18] fixed treewidth O(1) LP (flow) [35, 13] fixed treewidth 1 dynamic programming...
...Accordingly, our LP is larger and (possibly much) stronger than the standard flow LP, and hence our rounding does not imply a bound on the flowcut gap (akin to rounding of the SDP relaxation in [
3
, 10, 2])...
...Its standard strengthening to an SDP relaxation (the SDP used by the known approximation algorithms of [
3
, 2]) was shown in [23, 25, 17] to have integrality gap Ω(log log n), even for uniform demands...
Eden Chlamtac
,
et al.
Approximating Sparsest Cut in Graphs of Bounded Treewidth
References
(45)
O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
(
Citations: 26
)
Amit Agarwal
,
Moses Charikar
,
Konstantin Makarychev
,
Yury Makarychev
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 573581, 2005
Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
(
Citations: 444
)
Farid Alizadeh
Journal:
Siam Journal on Optimization  SIAM J OPTIMIZATION
, 1993
Eigenvalues and Expanders
(
Citations: 377
)
Noga Alon
Journal:
Combinatorica
, vol. 6, no. 2, pp. 8396, 1986
A combinatorial, primaldual approach to semidefinite programs
(
Citations: 42
)
Sanjeev Arora
,
Satyen Kale
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 227236, 2007
Euclidean distortion and the sparsest cut
(
Citations: 93
)
Sanjeev Arora
,
James R. Lee
,
Assaf Naor
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 553562, 2005
Sort by:
Citations
(20)
A Tighter Insertionbased Approximation of the Crossing Number
(
Citations: 1
)
Markus Chimani Petr Hlineny
,
Petr Hlinený
Journal:
Computing Research Repository  CORR
, vol. abs/1104.5, 2011
On Graph Crossing Number and Edge Planarization
(
Citations: 1
)
Julia Chuzhoy
,
Yury Makarychev
,
Anastasios Sidiropoulos
Conference:
ACMSIAM Symposium on Discrete Algorithms  SODA
, pp. 10501069, 2011
A Reformulation of the AroraRaoVazirani Structure Theorem
Sanjeev Arora
,
James R. Lee
,
Sushant Sachdeva
Journal:
Computing Research Repository  CORR
, vol. abs/1102.1, 2011
P01501  Relationship between heat shock protein 70 and B amyloids in patients with alzheimer disease and vascular dementia
Y. Fu
,
S. Xiao
Journal:
European Psychiatry  EUR PSYCHIAT
, vol. 26, pp. 505505, 2011
Efficient Search in Networks Using Conductance
Qing Ke
,
Yuxiao Dong
,
Bin Wu
Conference:
Advances in Social Network Analysis and Mining  ASONAM
, 2011