A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem
From MaRDI portal
Publication:5317574
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
Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25)
Related Items (15)
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
This page was built for publication: A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem
