A Linear Programming Approach to Max-Sum Problem: A Review

By Tomáš Werner. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007

406 citations recorded by the source corpus.

Subfields: Computer Networks and Communications, Computer Vision and Pattern Recognition, Signal Processing

View Paper: https://www.semanticscholar.org/paper/f156f0c7ef3ac5274d92234cd3a3a40f9ca1fb94

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Computer Vision and Pattern Recognition

In Signal Processing

Citations in the corpus

Diverse M-Best Solutions in Markov Random Fields (2012, background): “A number of techniques solve a Linear Programming (LP) relaxation of this problem [36], which is given by relaxing the boolean constraints (2d) to the unit interval, i.”
Graph cut based image segmentation with connectivity priors (2008, background): “These techniques do not necessarily find the best lower bound (see [14] or review article [28]).”
1 Introduction to Dual Decomposition for Inference (2010, neutral): “One of these relaxations is in fact well-known to be equivalent to the dual decomposition approach discussed in this paper (Schlesinger, 1976; Guignard and Kim, 1987; Komodakis et al., 2010; Wainwright et al., 2005; Werner, 2007).”
Convergent Tree-Reweighted Message Passing for Energy Minimization (2006, methodology): “(Another counterexample due to Schlesinger is given in [ 34 ]).”
Advanced Structured Prediction (2014, methodology): “Such integer primal estimates can be obtained from the dual ones due to the complementary slackness condition and using heuristic local search or rounding procedures (Werner, 2007; Kolmogorov, 2006; Ravikumar et al., 2010).”
Hinge-Loss Markov Random Fields and Probabilistic Soft Logic (2015, methodology): “Many DD algorithms use coordinate descent, such as TRW-S (Kolmogorov, 2006), MSD (Werner, 2007), MPLP (Globerson and Jaakkola, 2007), and ADLP (Meshi and Globerson, 2011), Other DD algorithms use subgradient-based approaches (e.”
Feature Correspondence Via Graph Matching: Models and Global Optimization (2008, background): “These techniques do not necessarily find the best lower bound (see [32] or review article [33]).”
Structured Learning and Prediction in Computer Vision (2011, methodology): “This derivation is similar to recently proposed efficient MAP inference algorithms, such as in [64, 82, 160, 162].”
MRF Energy Minimization and Beyond via Dual Decomposition (2011, neutral): “They rely on the following linear integer program, which can be shown to be equivalent to the task of minimizing the MRF energy (1) [40], [7], [53]: min x Eð ; xÞ ¼ Áx ¼ X p2V p Áx p þ X pq2E pq Áx pq ; s:t: x 2 X G ;”
Edge and line oriented contour detection: State of the art (2011, methodology): “The most important methods are graph diffusion [152], belief propagation [153], convex combination of trees [154,155], max-sum diffusion, and the augmenting directed acyclic graph algorithm [149].”
Hinge-Loss Markov Random Fields and Probabilistic Soft Logic (2015, background): “Many DD algorithms use coordinate descent, such as TRW-S (Kolmogorov, 2006), MSD (Werner, 2007), MPLP (Globerson and Jaakkola, 2007), and ADLP (Meshi and Globerson, 2011).”
Minimizing Nonsubmodular Functions with Graph Cuts-A Review (2007, background): “The term repameterization was introduced in the machine learning community [13], [34] (an alternative term for this is equivalent transformations [25], [36]).”
Distributed message passing for large scale graphical models (2011, methodology): “paradigm of distributed systems, such as Amazon EC2, and develop a new algorithm that is able to distribute and parallelize the computation and memory requirements while conserving the convergence and optimality guarantees of recent message-passing algorithms [8, 29, 4, 11, 7].”