Approximating the cone of copositive kernels to estimate the stability number of infinite graphs. (English) Zbl 1383.05220
Bassino, Frédérique (ed.) et al., LAGOS 2017. Selected papers of the 9th Latin-American algorithms, graphs, and optimization symposium, Marseille, France, September 11–15, 2017. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 62, 303-308 (2017).
Summary: It has been shown that the stable set problem in an infinite compact graph, and particularly the kissing number problem, reduces to an optimization problem over the cone of copositive kernels. We propose two converging hierarchies approximating this cone. Both are extensions of existing inner hierarchies for the finite dimensional copositive cone. We implement the first two levels of the new hierarchies for the kissing number problem.
For the entire collection see [Zbl 1383.05001].
For the entire collection see [Zbl 1383.05001].
References:
| [1] | Bachoc, C.; Vallentin, F., New upper bounds for kissing numbers from semidefinite programming, J. Amer. Math. Soc., 21, 3, 909-924 (2008) · Zbl 1223.90039 |
| [2] | de Klerk, E.; Pasechnik, D., Approximation of the stability number of a graph via copositive programming, SIAM J. Optim., 12, 875-892 (2002) · Zbl 1035.90058 |
| [3] | Delsarte, P.; Goethals, J. M.; Seidel, J. J., Spherical codes and designs, Geom. Dedicata, 6, 363-388 (1977) · Zbl 0376.05015 |
| [4] | Dobre, C.; Dur, M.; Frerick, L.; Vallentin, F., A Copositive Formulation for the Stability Number of Infinite Graphs, Math. Program., 160, 1, 65-83 (2016) · Zbl 1361.05091 |
| [5] | de Laat, D., Moment methods in extremal geometry (2016), Delft University of Technology, Ph.D. thesis |
| [6] | de Laat, D.; Vallentin, F., A semidefinite programming hierarchy for packing problems in discrete geometry, Math. Program., 151, 2, 529-553 (2015) · Zbl 1328.90102 |
| [7] | Motzkin, T. S.; Straus, E. G., Maxima for graphs and a new proof of a theorem of Turán, Canad. J. Math., 17, 533-540 (1965) · Zbl 0129.39902 |
| [8] | Parrilo, P., Structured Semidefinite Programming and Algebraic Geometry Methods in Robustness and Optimization (2000), California Institute of Technology: California Institute of Technology Pasadena, CA, Ph.D. thesis |
| [9] | Peña, J.; Vera, J. C.; Zuluaga, L. F., Computing the stability number of a graph via linear and semidefinite programming, SIAM J. Optim., 18, 2, 87-105 (2007) · Zbl 1176.90611 |
| [10] | Powers, V.; Reznick, B., A new bound for Pólya’s Theorem with Applications to Polynomials Positive on Polyhedra, Journal of Pure and Applied Algebra, 164, 1-2, 221-229 (2001) · Zbl 1075.14523 |
| [11] | Schoenberg, I. J., Positive definite functions on spheres, Duke Math. J., 9, 1, 96-108 (1942) · Zbl 0063.06808 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
