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
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.