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

DOI10.1137/S0895480101396937zbMath1077.68036MaRDI 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 algorithm; linear program; metric labeling; truncated linear metric

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90C59: Approximation methods and heuristics in mathematical programming

68W25: Approximation algorithms

Related Items

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

Uses Software

• EMD