A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem
From MaRDI portal
Publication:5317574
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
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