On earthmover distance, metric labeling, and 0-extension

DOI10.1137/070685671zbMATH Open1200.68121OpenAlexW2050972259MaRDI QIDQ3558006FDOQ3558006

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

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

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)

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
• Title not available (Why is that?)
• Minimum 0-extension problems on directed metrics
• 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)