Computing the stability number of a graph via linear and semidefinite programming
Javier Pena (jfpandrew.cmu.edu)
Abstract: We study certain linear and semidefinite programming lifting approximation schemes for computing the stability number of a graph. Our work is based on, and refines De Klerk and Pasechnik's approach to approximating the stability number via copositive programming (SIAM J. Optim. 12 (2002), 875--892). We provide a closed-form expression for the values computed by the linear programming approximations. We also show that the exact value of the stability number $\alpha(G)$ is attained by the semidefinite approximation of order $\alpha(G)-1$ as long as $\alpha(G) \leq 6$. Our results reveal some sharp differences between the linear and the semidefinite approximations. For instance, the value of the linear programming approximation of any order is strictly larger than $\alpha(G)$ whenever $\alpha(G) > 1$.
Keywords: stability number, copositivity, polynomials, lifting procedures
Category 1: Combinatorial Optimization (Other )
Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )
Citation: SIAM Journal on Optimization 18 (2007) pp. 87--105.
Entry Submitted: 04/08/2005
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|