The Hardness of Metric Labeling
From MaRDI portal
Publication:5422491
DOI10.1137/06065430XzbMath1124.68038MaRDI QIDQ5422491
Joseph (Seffi) Naor, Julia Chuzhoy
Publication date: 22 October 2007
Published in: SIAM Journal on Computing (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Approximation Algorithm for Cycle-Star Hub Network Design Problems and Cycle-Metric Labeling Problems, Simplex Partitioning via Exponential Clocks and the Multiway-Cut Problem, Unnamed Item, Simplex Transformations and the Multiway Cut Problem, Approximation algorithms for the single allocation problem in hub-and-spoke networks and related metric labeling problems, Hardness of approximation for crossing number, Approximation Algorithm for Cycle-Star Hub Network Design Problems and Cycle-Metric Labeling Problems