The DOI matches its Crossref record; 13 of the 13 references it cites were found in a registry or an index.
Roof duality, complementation and persistency in quadratic 0–1 optimization
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
The complexity of theorem-proving procedures
Cook, S. A. (1971) · Proceedings of the third annual ACM symposium on Theory of computing - STOC '71 · doi:10.1145/800157.805047 · Cited by 6,385
An analysis of approximations for maximizing submodular set functions—I
Nemhauser, G. L., Wolsey, L. A., & Fisher, M. L. (1978) · Mathematical Programming · doi:10.1007/bf01588971 · Cited by 4,412
Combinatorial optimization: networks and matroids
Lawler, E. L. (2021) · Cited by 3,359
A linear-time algorithm for testing the truth of certain quantified boolean formulas
Aspvall, B., Plass, M. F., & Tarjan, R. E. (1979) · Information Processing Letters · doi:10.1016/0020-0190(79)90002-4 · Cited by 892
Vertex packings: Structural properties and algorithms
Nemhauser, G. L., & Trotter, L. E. (1975) · Mathematical Programming · doi:10.1007/bf01580444 · Cited by 664
Boolean Methods in Operations Research and Related Areas
Hammer, P. L., & Rudeanu, S. (1968) · Ökonometrie und Unternehmensforschung / Econometrics and Operations Research · doi:10.1007/978-3-642-85823-9 · Cited by 529
Self-citationGallo, G., Hammer, P. L., & Simeone, B. (1980) · Mathematical Programming Studies · doi:10.1007/bfb0120892 · Cited by 286
Self-citationA Selection Problem of Shared Fixed Costs and Network Flows
Rhys, J. M. W. (1970) · Management Science · doi:10.1287/mnsc.17.3.200 · Cited by 239
Methods of Nonlinear 0-1 Programming
Hansen, P. (1979) · Annals of Discrete Mathematics · doi:10.1016/s0167-5060(08)70343-1 · Cited by 220
Self-citationVertices Belonging to All or to No Maximum Stable Sets of a Graph
Hammer, P. L., Hansen, P., & Simeone, B. (1982) · SIAM Journal on Algebraic and Discrete Methods · doi:10.1137/0603052 · Cited by 58
Self-citation
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
Boros, E., & Hammer, P. L. (2002) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(01)00341-9 · Cited by 827
Self-citationLearning human activities and object affordances from RGB-D videos
Koppula, H. S., Gupta, R., & Saxena, A. (2013) · The International Journal of Robotics Research · doi:10.1177/0278364913478446 · 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
Cluster analysis and mathematical programming
Hansen, P., & Jaumard, B. (1997) · Mathematical Programming · doi:10.1007/bf02614317 · Cited by 646
Self-citationAnticipating Human Activities Using Object Affordances for Reactive Robotic Response
Koppula, H. S., & Saxena, A. (2016) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2015.2430335 · Cited by 596
Non-convex mixed-integer nonlinear programming: A survey
Burer, S., & Letchford, A. N. (2012) · Surveys in Operations Research and Management Science · doi:10.1016/j.sorms.2012.08.001 · Cited by 547
Optimizing Binary MRFs via Extended Roof Duality
Rother, C., Kolmogorov, V., Lempitsky, V., & Szummer, M. (2007) · 2007 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2007.383203 · Cited by 427
Feature Correspondence Via Graph Matching: Models and Global Optimization
Torresani, L., Kolmogorov, V., & Rother, C. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-88688-4_44 · Cited by 388
Graph cut based image segmentation with connectivity priors
Vicente, S., Kolmogorov, V., & Rother, C. (2008) · 2008 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2008.4587440 · Cited by 385
Discovering social circles in ego networks
Mcauley, J., & Leskovec, J. (2014) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/2556612 · Cited by 366
Minimizing Nonsubmodular Functions with Graph Cuts-A Review
Kolmogorov, V., & Rother, C. (2007) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2007.1031 · Cited by 362
Algorithms for the maximum satisfiability problem
Hansen, P., & Jaumard, B. (1990) · Computing · doi:10.1007/bf02241270 · Cited by 360
Self-citationA Linear Programming Approach to Max-Sum Problem: A Review
Werner, T. (2007) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2007.1036 · Cited by 342
Reconstructing building interiors from images
Furukawa, Y., Curless, B., Seitz, S. M., & Szeliski, R. (2009) · 2009 IEEE 12th International Conference on Computer Vision · doi:10.1109/iccv.2009.5459145 · Cited by 315
Training structural SVMs when exact inference is intractable
Finley, T., & Joachims, T. (2008) · Proceedings of the 25th international conference on Machine learning - ICML '08 · doi:10.1145/1390156.1390195 · Cited by 260
A convex relaxation approach for computing minimal partitions
Pock, T., Chambolle, A., Cremers, D., & Bischof, H. (2009) · 2009 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2009.5206604 · Cited by 253
Transformation of General Binary MRF Minimization to the First-Order Case
Ishikawa, H. (2011) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2010.91 · Cited by 144
On Quadratization of Pseudo-Boolean Functions
Boros, E., & Gruber, A. (2014) · arXiv · doi:10.48550/arxiv.1404.6538 · Cited by 32
Metadata
- Authors
- Hammer, P. L., Hansen, P., & Simeone, B.
- Venue
- Mathematical Programming
- Published
- 1984-02
- Volume
- 28
- Issue
- 2
- Pages
- 121-155
- ISSN
- 0025-5610 (ISSN-L)
- 1436-4646
- OpenAlex
- W2006293258
- Cited by
- 316
- References
- 13
- FWCI
- 4.05
- 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.