On Earthmover Distance, Metric Labeling, and 0-Extension

DOI10.1137/070685671zbMath1200.68121OpenAlexW2050972259MaRDI QIDQ3558006

Subhash A. Khot, Yuval Rabani, Aranyak Mehta, Howard J. 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

0-extensionmetric labelingmultiway cutearthmover distance

Mathematics Subject Classification ID

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

Related Items (8)

Simplex Partitioning via Exponential Clocks and the Multiway-Cut Problem ⋮ Unnamed Item ⋮ Hardness of approximation for crossing number ⋮ Weakly Modular Graphs and Nonpositive Curvature ⋮ Retracting Graphs to Cycles ⋮ Simplex Transformations and the Multiway Cut Problem ⋮ Isometric structure of transportation cost spaces on finite metric spaces ⋮ On Lipschitz extension from finite subsets

This page was built for publication: On Earthmover Distance, Metric Labeling, and 0-Extension