Metric clustering via consistent labeling

DOI10.4086/TOC.2011.V007A005MaRDI QIDQ3002830zbMATH OpenOpenAlexFDO

Authors Robert Krauthgamer, Tim Roughgarden

Publication date 24 May 2011

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2011.v007a005

zbMATH Keywords

approximation algorithmsdecompositionmetric spaces

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Approximation algorithms for the metric labeling problem via a new linear programming formulation
• Approximate clustering via metric partitioning
• The Hardness of Metric Labeling
• A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem
• Approximating min-sum k -clustering in metric spaces

Cited in

(7)

• Squarepants in a tree: sum of subtree clustering and hyperbolic pants decomposition
• Graph Clustering using Effective Resistance
• Algorithms for metric learning via contrastive embeddings
• Cutting Corners Cheaply, or How to Remove Steiner Points
• Squarepants in a tree, sum of subtree clustering and hyperbolic pants decomposition
• Relaxed Voronoi: a simple framework for terminal-clustering problems
• Lipschitz decompositions of finite _p metrics

This page was built for publication: Metric clustering via consistent labeling

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