The DOI matches its Crossref record; 9 of the 9 references it cites were found in a registry or an index.
Cones of Matrices and Set-Functions and 0–1 Optimization
Abstract
It has been recognized recently that to represent a polyhedron as the projection of a higher-dimensional, but simpler, polyhedron, is a powerful tool in polyhedral combinatorics. A general method is developed to construct higher-dimensional polyhedra (or, in some cases, convex sets) whose projection approximates the convex hull of 0–1 valued solutions of a system of linear inequalities. An important feature of these approximations is that one can optimize any linear objective function over them in polynomial time. In the special case of the vertex packing polytope, a sequence of systems of inequalities is obtained such that the first system already includes clique, odd hole, odd antihole, wheel, and orthogonality constraints. In particular, for perfect (and many other) graphs, this first system gives the vertex packing polytope. For various classes of graphs, including t-perfect graphs, it follows that the stable set polytope is the projection of a polytope with a polynomial number of facets. An extension of the method is also discussed which establishes a connection with certain submodular functions and the Möbius function of a lattice.
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
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
Self-citationThe 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
Self-citationStanley, R. P. (1986) · Springer eBooks · doi:10.1007/978-1-4615-9763-6 · Cited by 1,796
Maximum matching and a polyhedron with 0,1-vertices
Edmonds, J. (1965) · Journal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics · doi:10.6028/jres.069b.013 · Cited by 1,712
On the foundations of combinatorial theory I. Theory of M�bius Functions
Rota, G. C. (1964) · Zeitschrift f�r Wahrscheinlichkeitstheorie und Verwandte Gebiete · doi:10.1007/bf00531932 · Cited by 1,476
Sherali, H. D., & Adams, W. P. (1990) · SIAM Journal on Discrete Mathematics · doi:10.1137/0403036 · Cited by 931
Edmonds polytopes and a hierarchy of combinatorial problems
Chvátal, V. (1973) · Discrete Mathematics · doi:10.1016/0012-365x(73)90167-2 · Cited by 624
On certain polytopes associated with graphs
Chvátal, V. (1975) · Journal of Combinatorial Theory Series B · doi:10.1016/0095-8956(75)90041-6 · Cited by 604
The perfectly Matchable Subgraph Polytope of an arbitrary graph
Balas, E., & Pulleyblank, W. R. (1989) · COMBINATORICA · doi:10.1007/bf02125345 · Cited by 51
Cited by
Vandenberghe, L., & Boyd, S. (1996) · SIAM Review · doi:10.1137/1038003 · Cited by 4,105
Goemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587
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
Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization
Parrilo, P. A. (2000) · doi:10.7907/2k6y-ch43 · Cited by 1,802
Semidefinite programming relaxations for semialgebraic problems
Parrilo, P. A. (2003) · Mathematical Programming · doi:10.1007/s10107-003-0387-5 · Cited by 1,527
Bomze, I. M., Budinich, M., Pardalos, P. M., & Pelillo, M. (1999) · Handbook of Combinatorial Optimization · doi:10.1007/978-1-4757-3023-4_1 · Cited by 1,148
Marked Decline in Atmospheric Carbon Dioxide Concentrations During the Paleogene
Pagani, M., Zachos, J. C., Freeman, K. H., Tipple, B., & Bohaty, S. (2005) · Science · doi:10.1126/science.1110063 · Cited by 902
Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
Alizadeh, F. (1995) · SIAM Journal on Optimization · doi:10.1137/0805002 · Cited by 892
High-Dimensional Statistics: A Non-Asymptotic Viewpoint
Wainwright, M. J. (2019) · Cambridge University Press eBooks · doi:10.1017/9781108627771 · Cited by 882
A survey for the quadratic assignment problem
Loiola, E. M., de Abreu, N. M. M., Boaventura-Netto, P. O., Hahn, P., & Querido, T. (2007) · European Journal of Operational Research · doi:10.1016/j.ejor.2005.09.032 · Cited by 741
A Direct Formulation for Sparse PCA Using Semidefinite Programming
d'Aspremont, A., El Ghaoui, L., Jordan, M. I., & Lanckriet, G. R. G. (2007) · SIAM Review · doi:10.1137/050645506 · Cited by 678
Sums of Squares, Moment Matrices and Optimization Over Polynomials
Laurent, M. (2009) · The IMA Volumes in Mathematics and its Applications · doi:10.1007/978-0-387-09686-5_7 · Cited by 648
Semidefinite programming for optimal power flow problems
Bai, X., Wei, H., Fujisawa, K., & Wang, Y. (2008) · International Journal of Electrical Power & Energy Systems · doi:10.1016/j.ijepes.2007.12.003 · Cited by 573
Phase recovery, MaxCut and complex semidefinite programming
Waldspurger, I., d’Aspremont, A., & Mallat, S. (2015) · Mathematical Programming · doi:10.1007/s10107-013-0738-9 · Cited by 573
Using Linear Programming to Decode Binary Linear Codes
Feldman, J., Wainwright, M. J., & Karger, D. R. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2004.842696 · Cited by 572
Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning
Morrison, D. R., Jacobson, S. H., Sauppe, J. J., & Sewell, E. C. (2016) · Discrete Optimization · doi:10.1016/j.disopt.2016.01.005 · Cited by 563
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
A Spectral Bundle Method for Semidefinite Programming
Helmberg, C., & Rendl, F. (2000) · SIAM Journal on Optimization · doi:10.1137/s1052623497328987 · Cited by 436
Hypothalamic POMC neurons promote cannabinoid-induced feeding
Koch, M., Varela, L., Kim, J. G., Kim, J. D., Hernández-Nuño, F., Simonds, S. E., Castorena, C. M., Vianna, C. R., Elmquist, J. K., Morozov, Y. M., et al. (2015) · Nature · doi:10.1038/nature14260 · Cited by 434
Expander flows, geometric embeddings and graph partitioning
Arora, S., Rao, S., & Vazirani, U. (2009) · Journal of the ACM · doi:10.1145/1502793.1502794 · Cited by 418
Interior Point Methods for Nonlinear Optimization
Pólik, I., & Terlaky, T. (2010) · Lecture Notes in Mathematics · doi:10.1007/978-3-642-11339-0_4 · Cited by 394
Sherali, H. D., & Adams, W. P. (1994) · Discrete Applied Mathematics · doi:10.1016/0166-218x(92)00190-w · Cited by 393
Semidefinite relaxation and nonconvex quadratic optimization
Nesterov, Y. (1998) · Optimization Methods and Software · doi:10.1080/10556789808805690 · Cited by 375
A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
Laurent, M. (2003) · Mathematics of Operations Research · doi:10.1287/moor.28.3.470.16391 · Cited by 373
Approximation of the Stability Number of a Graph via Copositive Programming
de Klerk, E., & Pasechnik, D. V. (2002) · SIAM Journal on Optimization · doi:10.1137/s1052623401383248 · Cited by 322
Expander flows, geometric embeddings and graph partitioning
Arora, S., Rao, S., & Vazirani, U. (2004) · Proceedings of the thirty-sixth annual ACM symposium on Theory of computing · doi:10.1145/1007352.1007355 · Cited by 297
Knuth, D. E. (1994) · The Electronic Journal of Combinatorics · doi:10.37236/1193 · Cited by 296
Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization
Benson, S. J., Ye, Y., & Zhang, X. (2000) · SIAM Journal on Optimization · doi:10.1137/s1052623497328008 · Cited by 276
Kammerdiner, A., Gevezes, T., Pasiliao, E., Pitsoulis, L., & Pardalos, P. M. (2013) · Encyclopedia of Operations Research and Management Science · doi:10.1007/978-1-4419-1153-7_1152 · Cited by 273
Resolution of Conflicts Involving Many Aircraft via Semidefinite Programming
Frazzoli, E., Mao, Z.-H., Oh, J.-H., & Feron, E. (2001) · Journal of Guidance, Control, and Dynamics · doi:10.2514/2.4678 · Cited by 269
Linear Level Lasserre Lower Bounds for Certain k-CSPs
Schoenebeck, G. (2008) · 2008 49th Annual IEEE Symposium on Foundations of Computer Science · doi:10.1109/focs.2008.74 · Cited by 261
An Introduction to Polynomial and Semi-Algebraic Optimization
Lasserre, J. B. (2015) · Cambridge University Press eBooks · doi:10.1017/cbo9781107447226 · Cited by 260
Learning dynamic polynomial proofs
Fawzi, A., Malinowski, M., Fawzi, H., & Fawzi, O. (2019) · arXiv · doi:10.48550/arxiv.1906.01681 · Cited by 8
Metadata
- Authors
- Lovász, L., & Schrijver, A.
- Venue
- SIAM Journal on Optimization
- Published
- 1991-05
- Volume
- 1
- Issue
- 2
- Pages
- 166-190
- ISSN
- 1052-6234 (ISSN-L)
- 1095-7189
- OpenAlex
- W2106264302
- Cited by
- 1,008
- References
- 9
- FWCI
- 3.31
- 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.