Approximation algorithms for the 0-extension problem

MaRDI QIDQ2768266zbMATH OpenFDO

Authors Gruia Calinescu, Yuval Rabani, Howard Karloff

Publication date 30 June 2002

zbMATH Keywords

approximation algorithmsgraph partitioningmetric relaxation

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Distance in graphs (05C12)

Recommendations

• Approximation Algorithms for the 0-Extension Problem
• scientific article; zbMATH DE number 2079348
• On earthmover distance, metric labeling, and 0-extension
• On earthmover distance, metric labeling, and 0-extension
• Approximation algorithms for the metric labeling problem via a new linear programming formulation

Cited in

(25)

• Parameterized algorithms for zero extension and metric labelling problems
• Relations between scaling exponents in unimodular random graphs
• Volume distortion for subsets of Euclidean spaces
• Approximation algorithms for polynomial-expansion and low-density graphs
• A simple algorithm for the multiway cut problem
• A tight bound on approximating arbitrary metrics by tree metrics
• Local embeddings of metric spaces
• Euclidean distortion and the sparsest cut
• scientific article; zbMATH DE number 4081306 (Why is no real title available?)
• Relaxed Voronoi: a simple framework for terminal-clustering problems
• Extending Lipschitz functions via random metric partitions
• Simplex partitioning via exponential clocks and the multiway-cut problem
• A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem
• Approximation Algorithms for the 0-Extension Problem
• Cutting Corners Cheaply, or How to Remove Steiner Points
• Graph Clustering using Effective Resistance
• Advances in metric embedding theory
• Minimum 0-extension problems on directed metrics
• scientific article; zbMATH DE number 2079348 (Why is no real title available?)
• On earthmover distance, metric labeling, and 0-extension
• Metric extension operators, vertex sparsifiers and Lipschitz extendability
• Minimum violation vertex maps and their applications to cut problems
• Absolute Lipschitz extendability
• Diffusive estimates for random walks on stationary random graphs of polynomial growth
• On earthmover distance, metric labeling, and 0-extension

This page was built for publication: Approximation algorithms for the 0-extension problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2768266)