TY - GEN

T1 - Metric extension operators, vertex sparsifiers and Lipschitz extendability

AU - Makarychev, Konstantin

AU - Makarychev, Yury

PY - 2010/12/1

Y1 - 2010/12/1

N2 - We study vertex cut and flow sparsifiers that were recently introduced by Moitra [23], and Leighton and Moitra [18]. 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 sparsi-fier, and improving the previous algorithmic upper bound of O(log2 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 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 1950s. Using this connection, we obtain a lower bound of Ω(√log k/log log k) for flow sparsifiers and a lower bound of Ω(√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 Õ(√log k) cut sparsifiers. On the other hand, any lower bound on cut sparsifiers better than Ω(√log k) would imply a negative answer to this question.

AB - We study vertex cut and flow sparsifiers that were recently introduced by Moitra [23], and Leighton and Moitra [18]. 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 sparsi-fier, and improving the previous algorithmic upper bound of O(log2 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 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 1950s. Using this connection, we obtain a lower bound of Ω(√log k/log log k) for flow sparsifiers and a lower bound of Ω(√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 Õ(√log k) cut sparsifiers. On the other hand, any lower bound on cut sparsifiers better than Ω(√log k) would imply a negative answer to this question.

UR - http://www.scopus.com/inward/record.url?scp=78751565448&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78751565448&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2010.31

DO - 10.1109/FOCS.2010.31

M3 - Conference contribution

AN - SCOPUS:78751565448

SN - 9780769542447

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 255

EP - 264

BT - Proceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010

T2 - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010

Y2 - 23 October 2010 through 26 October 2010

ER -