A copositive formulation for the stability number of infinite graphs

DOI10.1007/S10107-015-0974-2zbMATH Open1361.05091OpenAlexW3099124748MaRDI QIDQ344928FDOQ344928

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

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

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.

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

• 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?)
• 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
• 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 (6)

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

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)