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)
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (8)
Approximation Algorithm for Cycle-Star Hub Network Design Problems and Cycle-Metric Labeling Problems ⋮ Simplex Partitioning via Exponential Clocks and the Multiway-Cut Problem ⋮ A constant-ratio approximation algorithm for a class of hub-and-spoke network design problems and metric labeling problems: star metric case ⋮ Unnamed Item ⋮ Hardness of approximation for crossing number ⋮ Approximation Algorithm for Cycle-Star Hub Network Design Problems and Cycle-Metric Labeling Problems ⋮ Approximation algorithms for the single allocation problem in hub-and-spoke networks and related metric labeling problems ⋮ Simplex Transformations and the Multiway Cut Problem
This page was built for publication: The Hardness of Metric Labeling