Metric extension operators, vertex sparsifiers and Lipschitz extendability

Konstantin Makarychev*, Yury Makarychev

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

We study vertex cut and flow sparsifiers that were recently introduced by Moitra (2009), and Leighton and Moitra (2010). 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 known existential upper bound on the quality of a sparsifier, and improving the previous algorithmic upper bound of O(log2k/ 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 polynomialtime 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 obtain a lower bound of (Formula presented.) for flow sparsifiers and a lower bound of (Formula presented.) for cut sparsifiers. We show that if a certain open question posed by Ball in 1992 has a positive answer, then there exist (Formula presented.) cut sparsifiers. On the other hand, any lower bound on cut sparsifiers better than (Formula presented.) would imply a negative answer to this question.

Original languageEnglish (US)
Pages (from-to)913-959
Number of pages47
JournalIsrael Journal of Mathematics
Volume212
Issue number2
DOIs
StatePublished - May 1 2016

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Metric extension operators, vertex sparsifiers and Lipschitz extendability'. Together they form a unique fingerprint.

Cite this