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
(8)
Approximate Algorithm
Conduct Problems
Eigenvalues
Graph Partitioning
Normalized Cut
semidefinite program
semidefinite relaxation
Triangle Inequality
Related Publications
(63)
The Geometry of Graphs and Some of its Algorithmic Applications
Multicommodity maxflow mincut theorems and their use in designing approximation algorithms
Approximating minsum k clustering in metric spaces
Euclidean distortion and the sparsest cut
Embeddings of negativetype metrics and an improved approximation to generalized sparsest cut
Subscribe
Academic
Publications
Expander flows, geometric embeddings and graph partitioning
Expander flows, geometric embeddings and graph partitioning,10.1145/1007352.1007355,Sanjeev Arora,Satish Rao,Umesh V. Vazirani
Edit
Expander flows, geometric embeddings and graph partitioning
(
Citations: 216
)
BibTex

RIS

RefWorks
Download
Sanjeev Arora
,
Satish Rao
,
Umesh V. Vazirani
We give a O(√log n)approximation algorithm for sparsest cut, 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 "certificate" for a graph's expansion, by embedding an nnode expander in it with appropriate dilation and congestion. We call this an expander flow.
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 222231, 2004
DOI:
10.1145/1007352.1007355
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
)
(
www.cc.gatech.edu
)
(
reference.kfupm.edu.sa
)
(
www.informatik.unitrier.de
)
(
doi.acm.org
)
(
www.cs.princeton.edu
)
(
portal.acm.org
)
(
www.cs.ust.hk
)
(
www.cs.princeton.edu
)
More »
Citation Context
(150)
...This connection has inspired many spectral solutions to the problem, including the AroraRaoVazirani algorithm [
11
] and the many works that followed.,One can also use any balanced 2partitioning algorithm to obtain an approximation to a balanced kpartitioning when k is a power of 2, losing at most a logn factor [
11
]...
Isabelle Stanton
,
et al.
Streaming graph partitioning for large distributed graphs
...Karger, Motwani, and Sudan [18] use an SDP relaxation and rounding strategy to approximate graph coloring, Skutella [33] uses an SDP to approximately solve a scheduling problem, and recently, Arora, Rao and V. Vazirani [
2
] use SDP to approximate graph partitioning problems...
Garud Iyengar
,
et al.
Approximating Semidefinite Packing Programs
...Proof: The NPHardness proof is based on the reduction from the NPHard Uniform Sparsest Cut [
26
] problem...
...Proof: We construct a reduction from the NPHard Uniform Sparsest Cut [
26
] problem...
Kayi Lee
,
et al.
CrossLayer Survivability in WDMBased Networks
...dinary graphs, i.e., hmb with i = = 2 for all i. Feige and Krauthgamer [8] prove an O(log2n) approximation ratio (see also [
3
])...
Changhui Choi
,
et al.
A semidefinite programming approach to the hypergraph minimum bisectio...
...Although there are no known approximation algorithms for this general problem, the theory community has developed approximation algorithms for numerous more specialized settings, such as sparsest cut [
4
] and various flavors of facility location [6, 8]. To the best of our knowledge, the problem in Volley does not map to any of these previously studied specializations...
Sharad Agarwal
,
et al.
Volley: Automated Data Placement for GeoDistributed Cloud Services
References
(57)
Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
(
Citations: 444
)
Farid Alizadeh
Journal:
Siam Journal on Optimization  SIAM J OPTIMIZATION
, 1993
Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems
(
Citations: 24
)
N. Garg
Conference:
IEEE Symposium on Foundations of Computer Science  FOCS
, 1997
Defect detection in pipes using guided waves
(
Citations: 84
)
M. J. S. Lowe
,
D. N. Alleyne
,
P. Cawley
Journal:
Ultrasonics
, vol. 36, no. 1, pp. 147154, 1998
Interiorpoint polynomial methods in convex programming
(
Citations: 443
)
Y. Nesterov
,
A. Nemirovsky
Published in 1994.
CBMS Regional Conference Series in Mathematics
(
Citations: 41
)
Fan R. K. Chung
Published in 1997.
Sort by:
Citations
(216)
Streaming graph partitioning for large distributed graphs
Isabelle Stanton
,
Gabriel Kliot
Published in 2012.
Approximating Semidefinite Packing Programs
(
Citations: 2
)
Garud Iyengar
,
David J. Phillips
,
Clifford Stein
Published in 2011.
CrossLayer Survivability in WDMBased Networks
(
Citations: 1
)
Kayi Lee
,
Eytan Modiano
,
HyangWon Lee
Journal:
IEEE/ACM Transactions on Networking  TON
, vol. 19, no. 4, pp. 10001013, 2011
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