Capacitated metric labeling

MaRDI QIDQ5365095zbMATH OpenFDO

Authors Ankur Moitra, Matthew Andrews, Mohammad T. Hajiaghayi, Howard Karloff

Publication date 29 September 2017

Full work available at URL http://dl.acm.org/citation.cfm?id=2133112

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Recommendations

• The Hardness of Metric Labeling
• Approximation algorithms for the metric labeling problem via a new linear programming formulation
• The Capacitated K-Center Problem
• A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem
• A constant factor approximation algorithm for a class of classification problems

Cited in

(2)

• Optimal cuts and partitions in tree metrics in polynomial time
• The Hardness of Metric Labeling

This page was built for publication: Capacitated metric labeling

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