Metric extension operators, vertex sparsifiers and Lipschitz extendability

DOI10.1007/s11856-016-1315-8zbMath1341.05104arXiv1006.4607OpenAlexW2401176303MaRDI QIDQ2630142

Konstantin Makarychev, Yury Makarychev

Publication date: 25 July 2016

Published in: Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1006.4607

zbMATH Keywords

polynomial-time algorithmcut sparsifiersflow sparsifiers

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Flows in graphs (05C21)

Related Items (15)

Terminal embeddings ⋮ An introduction to the Ribe program ⋮ Vertex Sparsification in Trees ⋮ Steiner Point Removal with Distortion $O(\log {k})$ using the Relaxed-Voronoi Algorithm ⋮ Spectral calculus and Lipschitz extension for barycentric metric spaces ⋮ Impossibility of almost extension ⋮ Refined Vertex Sparsifiers of Planar Graphs ⋮ Improved Guarantees for Vertex Sparsification in Planar Graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Routing in Undirected Graphs with Constant Congestion ⋮ Separators in region intersection graphs ⋮ An exponential lower bound for cut sparsifiers in planar graphs ⋮ Cutting Corners Cheaply, or How to Remove Steiner Points ⋮ On Lipschitz extension from finite subsets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On general minimax theorems
• Characterizations of almost surely continuous p-stable random Fourier series and strongly stationary processes
• Markov chains, Riesz transforms and Lipschitz maps
• Minimum 0-extensions of graph metrics
• Extending Lipschitz functions via random metric partitions
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Fréchet embeddings of negative type metrics
• Markov chains in smooth Banach spaces and Gromov-hyperbolic metric spaces
• Extensions and limits to vertex sparsification
• Projection Constants
• Extensions of Lipschitz mappings into a Hilbert space
• Factorizations of natural embeddings of $l^{n}_{p}$ into $L_{r}$, I
• The best constants in the Khintchine inequality
• Über die zusammenziehende und Lipschitzsche Transformationen
• Extension of range of functions
• Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size
• Some applications of Ball’s extension theorem
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Expander flows, geometric embeddings and graph partitioning
• Vertex Sparsifiers: New Results from Old Techniques

This page was built for publication: Metric extension operators, vertex sparsifiers and Lipschitz extendability