The DOI matches its Crossref record; 46 of the 46 references it cites were found in a registry or an index.
A Linear Programming Approach to Max-Sum Problem: A Review
Abstract
The max-sum labeling problem, defined as maximizing a sum of binary (i.e., pairwise) functions of discrete variables, is a general NP-hard optimization problem with many applications, such as computing the MAP configuration of a Markov random field. We review a not widely known approach to the problem, developed by Ukrainian researchers Schlesinger et al. in 1976, and show how it contributes to recent results, most importantly, those on the convex combination of trees and tree-reweighted max-product. In particular, we review Schlesinger et al.'s upper bound on the max-sum criterion, its minimization by equivalent transformations, its relation to the constraint satisfaction problem, the fact that this minimization is dual to a linear programming relaxation of the original problem, and the three kinds of consistency necessary for optimality of the upper bound. We revisit problems with Boolean variables and supermodular problems. We describe two algorithms for decreasing the upper bound. We present an example application for structural image analysis.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1988) · Cited by 16,582
Fast approximate energy minimization via graph cuts
Boykov, Y., Veksler, O., & Zabih, R. (2001) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.969114 · Cited by 6,988
Introduction to Lattices and Order
Davey, B. A., & Priestley, H. A. (2002) · Cambridge University Press eBooks · doi:10.1017/cbo9780511809088 · Cited by 4,901
Perceptrons: An Introduction to Computational Geometry
Minsky, M., & Papert, S. A. (1969) · Cited by 3,718
Geometric Algorithms and Combinatorial Optimization
Grötschel, M., Lovász, L., & Schrijver, A. (1988) · Algorithms and Combinatorics · doi:10.1007/978-3-642-97881-4 · Cited by 3,431
What energy functions can be minimized via graph cuts?
Kolmogorov, V., & Zabih, R. (2004) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2004.1262177 · Cited by 3,127
Consistency in networks of relations
Mackworth, A. K. (1977) · Artificial Intelligence · doi:10.1016/0004-3702(77)90007-8 · Cited by 2,498
The ellipsoid method and its consequences in combinatorial optimization
Grötschel, M., Lovász, L., & Schrijver, A. (1981) · Combinatorica · doi:10.1007/bf02579273 · Cited by 2,011
Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms
Yedidia, J. S., Freeman, W. T., & Weiss, Y. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.850085 · Cited by 1,617
Scene Labeling by Relaxation Operations
Rosenfeld, A., Hummel, R. A., & Zucker, S. W. (1976) · IEEE Transactions on Systems, Man, and Cybernetics · doi:10.1109/tsmc.1976.4309519 · Cited by 1,399
Encyclopedia of Artificial Intelligence
(2009) · IGI Global eBooks · doi:10.4018/978-1-59904-849-9 · Cited by 1,396
Minimizing a Submodular Function on a Lattice
Topkis, D. M. (1978) · Operations Research · doi:10.1287/opre.26.2.305 · Cited by 1,315
Networks of constraints: Fundamental properties and applications to picture processing
Montanari, U. (1974) · Information Sciences · doi:10.1016/0020-0255(74)90008-5 · Cited by 1,275
Introduction to lattices and order
(1991) · Choice Reviews Online · doi:10.5860/choice.28-3334 · Cited by 1,122
Convergent Tree-Reweighted Message Passing for Energy Minimization
Kolmogorov, V. (2006) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2006.200 · Cited by 1,095
Exact Maximum A Posteriori Estimation for Binary Images
Greig, D. M., Porteous, B. T., & Seheult, A. H. (1989) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1989.tb01764.x · Cited by 1,055
Submodular functions and convexity
Lovász, L. (1983) · Mathematical Programming The State of the Art · doi:10.1007/978-3-642-68874-4_10 · Cited by 964
Linear Programming: Foundations and Extensions
Vanderbei, R. J. (1998) · Journal of the Operational Research Society · doi:10.1038/sj.jors.2600987 · Cited by 921
Boros, E., & Hammer, P. L. (2002) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(01)00341-9 · Cited by 827
The generalized distributive law
Aji, S. M., & McEliece, R. J. (2000) · IEEE Transactions on Information Theory · doi:10.1109/18.825794 · Cited by 735
A combinatorial strongly polynomial algorithm for minimizing submodular functions
Iwata, S., Fleischer, L., & Fujishige, S. (2001) · Journal of the ACM · doi:10.1145/502090.502096 · Cited by 683
MAP Estimation Via Agreement on Trees: Message-Passing and Linear Programming
Wainwright, M. J., Jaakkola, T. S., & Willsky, A. S. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.856938 · Cited by 654
A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial Time
Schrijver, A. (2000) · Journal of Combinatorial Theory, Series B · doi:10.1006/jctb.2000.1989 · Cited by 651
Semiring-based constraint satisfaction and optimization
Bistarelli, S., Montanari, U., & Rossi, F. (1997) · Journal of the ACM · doi:10.1145/256303.256306 · Cited by 630
Exact optimization for markov random fields with convex priors
Ishikawa, H. (2003) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2003.1233908 · Cited by 486
Generating Semantic Descriptions From Drawings of Scenes With Shadows
Waltz, D. L. (1972) · Defense Technical Information Center (DTIC) · Cited by 441
A Comparative Study of Energy Minimization Methods for Markov Random Fields
Szeliski, R., Zabih, R., Scharstein, D., Veksler, O., Kolmogorov, V., Agarwala, A., Tappen, M., & Rother, C. (2006) · Lecture Notes in Computer Science · doi:10.1007/11744047_2 · Cited by 386
A New Class of Upper Bounds on the Log Partition Function
Wainwright, M. J., Jaakkola, T. S., & Willsky, A. S. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.850091 · Cited by 381
Roof duality, complementation and persistency in quadratic 0–1 optimization
Hammer, P. L., Hansen, P., & Simeone, B. (1984) · Mathematical Programming · doi:10.1007/bf02612354 · Cited by 316
The Consistent Labeling Problem: Part I
Haralick, R. M., & Shapiro, L. G. (1979) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1979.4766903 · Cited by 285
Semiring-Based CSPs and Valued CSPs: Frameworks, Properties, and Comparison
Stefano Bistarelli, B., Montanari, U., Rossi, F., Schiex, T., Verfaillie, G., & Fargier, H. (1999) · Constraints · doi:10.1023/a:1026441215081 · Cited by 272
Solving and analyzing side-chain positioning problems using linear and integer programming
Kingsford, C. L., Chazelle, B., & Singh, M. (2005) · Bioinformatics · doi:10.1093/bioinformatics/bti144 · Cited by 233
Tree-based reparameterization framework for analysis of sum-product and related algorithms
Wainwright, M. J., Jaakkola, T. S., & Willsky, A. S. (2003) · IEEE Transactions on Information Theory · doi:10.1109/tit.2003.810642 · Cited by 232
What Energy Functions Can Be Minimized via Graph Cuts?
Kolmogorov, V., & Zabih, R. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-47977-5_5 · Cited by 209
Some Network Flow Problems Solved with Pseudo-Boolean Programming
Ivănescu, P. L. (1965) · Operations Research · doi:10.1287/opre.13.3.388 · Cited by 170
Segmentation by grouping junctions
Ishikawa, H., & Geiger, D. (2002) · Proceedings. 1998 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (Cat. No.98CB36231) · doi:10.1109/cvpr.1998.698598 · Cited by 163
Linear Programming Relaxations and Belief Propagation -- An Empirical Study
Yanover, C., Meltzer, T., & Weiss, Y. (2006) · Journal of Machine Learning Research · doi:10.5555/1248547.1248615 · Cited by 153
Constraint solving via fractional edge covers
Grohe, M., & Marx, D. (2006) · Symposium on Discrete Algorithms · doi:10.5555/1109557.1109590 · Cited by 133
Tree consistency and bounds on the performance of the max-product algorithm and its generalizations
Wainwright, M. J., Jaakkola, T., & Willsky, A. S. (2004) · Statistics and Computing · doi:10.1023/b:stco.0000021412.33763.d5 · Cited by 125
Meltzer, T., Yanover, C., & Weiss, Y. (2005) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2005.110 · Cited by 109
Quadratic programming relaxations for metric labeling and Markov random field MAP estimation
Ravikumar, P., & Lafferty, J. (2006) · International Conference on Machine Learning · doi:10.1145/1143844.1143937 · Cited by 103
On the optimality of tree-reweighted max-product message-passingPreprint
Kolmogorov, V., & Wainwright, M. J. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1207.1395 · Cited by 98
TRANSFORMING AN ARBITRARY MINSUM PROBLEM INTO A BINARY ONE
Schlesinger, D., & Flach, B. (2006) · Cited by 96
Comparison of Energy Minimization Algorithms for Highly Connected Graphs
Kolmogorov, V., & Rother, C. (2006) · Lecture notes in computer science · doi:10.1007/11744047_1 · Cited by 67
Supermodular functions and the complexity of MAX CSP
Cohen, D. A., Cooper, M., Jeavons, P., & Krokhin, A. (2005) · Discrete Applied Mathematics · doi:10.1016/j.dam.2005.03.003 · Cited by 34
MAP Estimation via Agreement on (Hyper)trees: Message-passing and Linear Programming Approaches
Communication, A. C. O., Wainwright, M. J., Jaakkola, T., & Willsky, A. S. (2002) · Cited by 22
Cited by
Graphical Models, Exponential Families, and Variational Inference
Wainwright, M. J., & Jordan, M. I. (2007) · now publishers, Inc. eBooks · doi:10.1561/9781601981851 · Cited by 2,959
Graphical Models, Exponential Families, and Variational Inference
Wainwright, M. J., & Jordan, M. I. (2008) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000001 · Cited by 1,820
Convergent Tree-Reweighted Message Passing for Energy Minimization
Kolmogorov, V. (2006) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2006.200 · Cited by 1,095
Optimization for Machine Learning
(2011) · The MIT Press eBooks · doi:10.7551/mitpress/8996.001.0001 · Cited by 875
Komodakis, N., & Pesquet, J.-C. (2015) · IEEE Signal Processing Magazine · doi:10.1109/msp.2014.2377273 · Cited by 419
Metadata
- Authors
- Werner, T.
- Venue
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- Published
- 2007-07
- Volume
- 29
- Issue
- 7
- Pages
- 1165-1179
- ISSN
- 0162-8828 (ISSN-L)
- OpenAlex
- W2135414191
- Cited by
- 342
- References
- 46
- FWCI
- 31.52
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.