The DOI matches its Crossref record; 20 of the 20 references it cites were found in a registry or an index.
Approximation of the Stability Number of a Graph via Copositive Programming
Open accessAbstract
Lovász and Schrijver [SIAM J. Optim., 1 (1991), pp. 166--190] showed how to formulate increasingly tight approximations of the stable set polytope of a graph by solving semidefinite programs (SDPs) of increasing size (lift-and-project method). In this paper we present a similar idea. We show how the stability number can be computed as the solution of a conic linear program (LP) over the cone of copositive matrices. Subsequently, we show how to approximate the copositive cone ever more closely via a hierarchy of linear or semidefinite programs of increasing size (liftings). The latter idea is based on recent work by Parrilo [Structured Semidefinite Programs and Semi-algebraic Geometry Methods in Robustness and Optimization, Ph.D. thesis, California Institute of Technology, Pasadena, CA, 2000]. In this way we can compute the stability number $\alpha(G)$ of any graph $G(V,E)$ after at most $\alpha(G)^2$ successive liftings for the LP-based approximations. One can compare this to the $n - \alpha(G)-1$ bound for the LP-based lift-and-project scheme of Lovász and Schrijver. Our approach therefore requires fewer liftings for families of graphs where $\alpha(G) < O(\sqrt{n})$. We show that the first SDP-based approximation for $\alpha(G)$ in our series of increasingly tight approximations coincides with the $\vartheta'$-function of Schrijver [IEEE Trans. Inform. Theory, 25 (1979), pp. 425--429]. We further show that the second approximation is tight for complements of triangle-free graphs and for odd cycles.
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
Interior-Point Polynomial Algorithms in Convex Programming
Nesterov, Y., & Nemirovskii, A. (1994) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611970791 · Cited by 4,334
Spencer, J. (1991) · Medical Entomology and Zoology · Cited by 4,310
Goemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587
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
Global Optimization with Polynomials and the Problem of Moments
Lasserre, J. B. (2001) · SIAM Journal on Optimization · doi:10.1137/s1052623400366802 · Cited by 2,474
On the Shannon capacity of a graph
Lovasz, L. (1979) · IEEE Transactions on Information Theory · doi:10.1109/tit.1979.1055985 · Cited by 1,624
Coxeter, H. S. M. (1969) · Cited by 1,582
Clique is hard to approximate within n1−ε
Håstad, J. (1999) · Acta Mathematica · doi:10.1007/bf02392825 · Cited by 1,369
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
Cones of Matrices and Set-Functions and 0–1 Optimization
Lovász, L., & Schrijver, A. (1991) · SIAM Journal on Optimization · doi:10.1137/0801013 · Cited by 1,008
Cited by
Semidefinite programming relaxations for semialgebraic problems
Parrilo, P. A. (2003) · Mathematical Programming · doi:10.1007/s10107-003-0387-5 · Cited by 1,527
(2014) · Choice Reviews Online · doi:10.5860/choice.51-3296 · Cited by 1,260
Most Tensor Problems Are NP-Hard
Hillar, C. J., & Lim, L.-H. (2013) · Journal of the ACM · doi:10.1145/2512329 · Cited by 1,099
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
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
Metadata
- Authors
- de Klerk, E., & Pasechnik, D. V.
- Venue
- SIAM Journal on Optimization
- Published
- 2002-01
- Volume
- 12
- Issue
- 4
- Pages
- 875-892
- ISSN
- 1052-6234 (ISSN-L)
- 1095-7189
- OpenAlex
- W2120146316
- Cited by
- 322
- References
- 20
- FWCI
- 7.32
- Type
- journal article
- Language
- en
- Open access
- green
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Approximation of the Stability Number of a Graph via Copositive Programming. https://app.cochat.ai/papers/10.1137/s1052623401383248
- The paper
- de Klerk, E., & Pasechnik, D. V. (2002). Approximation of the Stability Number of a Graph via Copositive Programming. SIAM Journal on Optimization. https://doi.org/10.1137/s1052623401383248
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.