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

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

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)

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

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)