Approximate classification via earthmover metrics

zbMATH Open1318.68193MaRDI QIDQ5501372FDOQ5501372

Authors: Aaron Archer, Jittat Fakcharoenphol, Chris Harrelson, Robert Krauthgamer, Kunal Talwar, Éva Tardos 

Publication date: 3 August 2015

Recommendations

• 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
• Approximation Algorithms for the 0-Extension Problem
• A constant factor approximation algorithm for a class of classification problems

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25)

Cited In (9)

• Nonembeddability theorems via Fourier analysis
• On Lipschitz extension from finite subsets
• A tight bound on approximating arbitrary metrics by tree metrics
• Image labeling based on graphical models using Wasserstein messages and geometric assignment
• On earthmover distance, metric labeling, and 0-extension
• Approximating spaces of Nagata dimension zero by weighted trees
• Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs
• An explicit bound on the transportation cost distance
• On earthmover distance, metric labeling, and 0-extension

This page was built for publication: Approximate classification via earthmover metrics

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