Approximation Algorithms for the 0-Extension Problem
From MaRDI portal
Publication:4651539
DOI10.1137/S0097539701395978zbMath1087.68128MaRDI QIDQ4651539
Yuval Rabani, Gruia Călinescu, Howard J. Karloff
Publication date: 21 February 2005
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25)
Related Items (18)
Terminal embeddings ⋮ Metric decompositions of path-separable graphs ⋮ Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem ⋮ Making doubling metrics geodesic ⋮ Unnamed Item ⋮ Maximum gradient embeddings and monotone clustering ⋮ Unnamed Item ⋮ Steiner Point Removal with Distortion $O(\log {k})$ using the Relaxed-Voronoi Algorithm ⋮ Random martingales and localization of maximal inequalities ⋮ Ramsey partitions and proximity data structures ⋮ Quasimetric embeddings and their applications ⋮ Retracting Graphs to Cycles ⋮ Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs ⋮ Partitioning a graph into small pieces with applications to path transversal ⋮ Simplex Transformations and the Multiway Cut Problem ⋮ On \(L_1\)-embeddability of unions of \(L_1\)-embeddable metric spaces and of twisted unions of hypercubes ⋮ Light spanners for high dimensional norms via stochastic decompositions ⋮ On Lipschitz extension from finite subsets
This page was built for publication: Approximation Algorithms for the 0-Extension Problem
