On earthmover distance, metric labeling, and 0-extension

DOI10.1137/070685671MaRDI QIDQ3558006zbMATH OpenOpenAlexFDO

Authors Subhash Khot, Aranyak Mehta, Yuval Rabani, Howard Karloff

Publication date 29 April 2010

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/070685671

zbMATH Keywords

metric labelingmultiway cut0-extensionearthmover distance

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• On earthmover distance, metric labeling, and 0-extension
• Approximation algorithms for the 0-extension problem
• The Hardness of Metric Labeling
• Approximate classification via earthmover metrics
• Approximation Algorithms for the 0-Extension Problem

Cited in

(14)

• Retracting Graphs to Cycles
• Parameterized algorithms for zero extension and metric labelling problems
• On Lipschitz extension from finite subsets
• Approximate classification via earthmover metrics
• Simplex partitioning via exponential clocks and the multiway-cut problem
• Approximation Algorithms for the 0-Extension Problem
• Minimum 0-extension problems on directed metrics
• scientific article; zbMATH DE number 2079348 (Why is no real title available?)
• Weakly Modular Graphs and Nonpositive Curvature
• On earthmover distance, metric labeling, and 0-extension
• Simplex transformations and the multiway cut problem
• Hardness of approximation for crossing number
• Isometric structure of transportation cost spaces on finite metric spaces
• Approximation algorithms for the 0-extension problem

This page was built for publication: On earthmover distance, metric labeling, and 0-extension

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