A copositive formulation for the stability number of infinite graphs

DOI10.1007/S10107-015-0974-2zbMATH Open1361.05091arXiv1305.1819OpenAlexW3099124748MaRDI 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)

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Global optimization with polynomials and the problem of moments
• Title not available (Why is that?)
• Semidefinite programming relaxations for semialgebraic problems
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Positive definite functions on spheres
• Approximation of the stability number of a graph via copositive programming
• Title not available (Why is that?)
• Lectures on Choquet's theorem
• Spherical codes and designs
• Convexity. An analytic viewpoint
• On copositive programming and standard quadratic optimization problems
• On standard quadratic optimization problems
• Lower bounds for measurable chromatic numbers
• A semidefinite programming hierarchy for packing problems in discrete geometry
• Improved Delsarte bounds for spherical codes in small dimensions
• Hilbert distances and positive definite functions
• Scaling relationship between the copositive cone and Parrilo's first level approximation
• Spherical Sets Avoiding a Prescribed Set of Angles
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)