Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability

Konstantin Makarychev, Yury Makarychev

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 al…