LP Relaxation of the Potts Labeling Problem Is as Hard as Any Linear Program

In our recent work, we showed that solving the LP relaxation of the pairwise min-sum labeling problem (also known as MAP inference in graphical models or discrete energy minimization) is not much easier than solving any linear program. Precisely, the general linear program reduces in linear time (as...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on pattern analysis and machine intelligence 2017-07, Vol.39 (7), p.1469-1475
Main Authors: Prusa, Daniel, Werner, Tomas
Format: Article
Language:English
Subjects:
Approximation algorithms
Computation
Computational modeling
Cost function
discrete energy minimization
Energy conservation
graphical model
Graphical models
Inference
Labeling
Labels
linear programming relaxation
MAP inference
Marking
Markov random field
Mathematical models
Measurement
Minimization
Optimization
Potts model
uniform metric labeling problem
valued constraint satisfaction
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In our recent work, we showed that solving the LP relaxation of the pairwise min-sum labeling problem (also known as MAP inference in graphical models or discrete energy minimization) is not much easier than solving any linear program. Precisely, the general linear program reduces in linear time (assuming the Turing model of computation) to the LP relaxation of the min-sum labeling problem. The reduction is possible, though in quadratic time, even to the min-sum labeling problem with planar structure. Here we prove similar results for the pairwise min-sum labeling problem with attractive Potts interactions (also known as the uniform metric labeling problem).
ISSN:0162-8828
1939-3539
2160-9292
DOI:10.1109/TPAMI.2016.2582165