A Reformulation of the Arora-Rao-Vazirani Structure Theorem

Details A Reformulation of the Arora-Rao-Vazirani Structure Theorem A Reformulation of the Arora-Rao-Vazirani Structure Theorem

2011-02-07

arxiv.org/abs/1102.1456v1

Computer Science

Discrete Mathematics

4 pages

Scientific paper

In a well-known paper[ARV], Arora, Rao and Vazirani obtained an O(sqrt(log n)) approximation to the Balanced Separator problem and Uniform Sparsest Cut. At the heart of their result is a geometric statement about sets of points that satisfy triangle inequalities, which also underlies subsequent work on approximation algorithms and geometric embeddings. In this note, we give an equivalent formulation of the Structure theorem in [ARV] in terms of the expansion of large sets in geometric graphs on sets of points satisfying triangle inequalities.

Affiliated with

Also associated with

No associations

Rating

A Reformulation of the Arora-Rao-Vazirani Structure Theorem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Reformulation of the Arora-Rao-Vazirani Structure Theorem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Reformulation of the Arora-Rao-Vazirani Structure Theorem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-501761