Approximation of the Stability Number of a Graph via Copositive Programming

By Etienne de Klerk, Dmitrii V. Pasechnik. SIAM Journal on Optimization, 2002

375 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Real algebraic geometry (2013, background): “Other topics concerning the topology of real algebraic varieties that I was not able to treat, but would have deserved to be treated, are, among others: cobordism classes of real algebraic varieties and morphisms [61, 42](1), cohomology of real algebraic varieties [67, 32, 34, 63, 33, 20], equivaria”
Stability of polytopes of matrices via affine parameter-dependent lyapunov functions : Asymptotically exact LMI conditions (2005, methodology): “This strategy has also been used in [19,20] for stability analysis and in many other contexts involving copositive programming (see for instance [24]).”
Copositive Programming – a Survey (2010, methodology): “Using a somewhat different approach, De Klerk and Pasechnik [23] derive the following formulation for the stability number α(G):”
On Cones of Nonnegative Quadratic Functions (2003, neutral): “Recent results on approximating the usual co-positive cone by semidefinite programming can be found in Parrilo [15] and De Klerk and Pasechnik [9].”
On the copositive representation of binary and continuous nonconvex quadratic programs (2009, background): “– Can we extend the bounds on approximation error proved by Bomze and de Klerk [2] for standard quadratic programming? Even more interesting, can we extend the polynomial-time approximation scheme for standard quadratic programming to more general constraint structures? – Are there cases in which on”