Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability

Computer Science – Data Structures and Algorithms

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Appeared at FOCS 2010

Scientific paper

We study vertex cut and flow sparsifiers that were recently introduced by Moitra, and Leighton and Moitra. We improve and generalize their results. We give a new polynomial-time algorithm for constructing O(log k / log log k) cut and flow sparsifiers, matching the best existential upper bound on the quality of a sparsifier, and improving the previous algorithmic upper bound of O(log^2 k / log log k). We show that flow sparsifiers can be obtained from linear operators approximating minimum metric extensions. We introduce the notion of (linear) metric extension operators, prove that they exist, and give an exact polynomial-time algorithm for finding optimal operators. We then establish a direct connection between flow and cut sparsifiers and Lipschitz extendability of maps in Banach spaces, a notion studied in functional analysis since 1930s. Using this connection, we prove a lower bound of Omega(sqrt{log k/log log k}) for flow sparsifiers and a lower bound of Omega(sqrt{log k}/log log k) for cut sparsifiers. We show that if a certain open question posed by Ball in 1992 has a positive answer, then there exist \tilde O(sqrt{log k}) cut sparsifiers. On the other hand, any lower bound on cut sparsifiers better than \tilde Omega(sqrt{log k}) would imply a negative answer to this question.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability 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 Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-278560

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.