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
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