A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem

DOI10.1137/S0895480101396937zbMath1077.68036OpenAlexW1996540180MaRDI QIDQ5317574

Leonid Zosin, Chandra Chekuri, Joseph (Seffi) Naor, Sanjeev Khanna

Publication date: 16 September 2005

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895480101396937

zbMATH Keywords

approximation algorithmlinear programmetric labelingtruncated linear metric

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25)

Related Items

Sherali-Adams Relaxations for Valued CSPs, Simplex Partitioning via Exponential Clocks and the Multiway-Cut Problem, Shape-based object detection via boundary structure segmentation, The Power of Sherali--Adams Relaxations for General-Valued CSPs, GRMA: generalized range move algorithms for the efficient optimization of MRFs, A constant-ratio approximation algorithm for a class of hub-and-spoke network design problems and metric labeling problems: star metric case, Image Labeling Based on Graphical Models Using Wasserstein Messages and Geometric Assignment, Approximation algorithms for the single allocation problem in hub-and-spoke networks and related metric labeling problems, Retracting Graphs to Cycles, Solving LP Relaxations of Some NP-Hard Problems Is As Hard As Solving Any Linear Program, Simplex Transformations and the Multiway Cut Problem, The Power of Linear Programming for General-Valued CSPs, Unnamed Item, Unnamed Item, On Lipschitz extension from finite subsets

Uses Software

• EMD