A copositive formulation for the stability number of infinite graphs

DOI10.1007/S10107-015-0974-2MaRDI QIDQ344928zbMATH OpenOpenAlexFDO

Authors Cristian Dobre, Mirjam Dür, Leonhard Frerick, Frank Vallentin

Publication date 25 November 2016

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1305.1819

zbMATH Keywords

combinatorial optimizationcopositive programminginfinite graphsstability number

Mathematics Subject Classification ID

Infinite graphs (05C63) Applications of functional analysis in optimization, convex analysis, mathematical programming, economics (46N10) Convex programming (90C25) Nonconvex programming, global optimization (90C26) Combinatorial optimization (90C27)

Abstract: In the last decade, copositive formulations have been proposed for a variety of combinatorial optimization problems, for example the stability number (independence number). In this paper, we generalize this approach to infinite graphs and show that the stability number of an infinite graph is the optimal solution of some infinite-dimensional copositive program. For this we develop a duality theory between the primal convex cone of copositive kernels and the dual convex cone of completely positive measures. We determine the extreme rays of the latter cone, and we illustrate this theory with the help of the kissing number problem.

Review text

According to \textit{D. de Laat} and the last author [Math. Program. 151, No. 2 (B), 529--553 (2015; Zbl 1328.90102)], a topological packing graph is a graph (with possibly infinitely many vertices and edges) whose vertex set \(V\) is a Hausdorff topological space and whose every finite clique is contained in an open clique. The main result of the paper provides a formulation of the stability number of such a graph, in the case when \(V\) is compact and metrizable, as a linear conic problem with two variables; one of them is real and the other one is a symmetric and continuous function \(K:V\times V\rightarrow \mathbb{R}\) which is copositive in the sense that \(\int_{V}\int_{V}K\left( x,y\right) f\left( x\right) f\left( y\right) d\omega \left( x\right) d\omega \left( y\right) \geq 0\) for all nonnegative continuous function \(f:V\rightarrow \mathbb{R};\) here \(\omega \) denotes a probability measure which is strictly positive on open sets. This optimization problem has an analogous structure as the copositive formulation of the stability number of a finite graph due to \textit{E. de Klerk} and \textit{D. V. Pasechnik} [SIAM J. Optim. 12, No. 4, 875--892 (2002; Zbl 1035.90058)], which is actually an immediate corollary of the main result in the paper under review.

Recommendations

• Approximating the cone of copositive kernels to estimate the stability number of infinite graphs
• Approximation of the stability number of a graph via copositive programming
• Copositive programming motivated bounds on the stability and the chromatic numbers
• Copositive optimization -- recent developments and applications
• Contribution of copositive formulations to graph partitioning problem

Cites work

• A semidefinite programming hierarchy for packing problems in discrete geometry
• Approximation of the stability number of a graph via copositive programming
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Convexity. An analytic viewpoint
• Global optimization with polynomials and the problem of moments
• Hilbert distances and positive definite functions
• scientific article; zbMATH DE number 4004880 (Why is no real title available?)
• scientific article; zbMATH DE number 1022519 (Why is no real title available?)
• scientific article; zbMATH DE number 1860211 (Why is no real title available?)
• scientific article; zbMATH DE number 2115093 (Why is no real title available?)
• scientific article; zbMATH DE number 918597 (Why is no real title available?)
• scientific article; zbMATH DE number 3201668 (Why is no real title available?)
• Improved Delsarte bounds for spherical codes in small dimensions
• Lectures on Choquet's theorem
• Lower bounds for measurable chromatic numbers
• On copositive programming and standard quadratic optimization problems
• On standard quadratic optimization problems
• Positive definite functions on spheres
• Scaling relationship between the copositive cone and Parrilo's first level approximation
• Semidefinite programming relaxations for semialgebraic problems
• Spherical codes and designs
• Spherical sets avoiding a prescribed set of angles
• Upper bounds for packings of spheres of several radii

Cited in

(7)

• Copositivity and complete positivity. Abstracts from the workshop held October 29 -- Novermber 4, 2017
• Complete positivity and distance-avoiding sets
• Approximating the cone of copositive kernels to estimate the stability number of infinite graphs
• Approximation of the stability number of a graph via copositive programming
• Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems
• Measure-valued affine and polynomial diffusions
• Optimization hierarchies for distance-avoiding sets in compact spaces

This page was built for publication: A copositive formulation for the stability number of infinite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q344928)