logo IMB
Retour

Séminaire de Théorie des Nombres

Semidefinite programming bounds

Frank Vallentin

( Amsterdam )

Salle de Conférences

le 17 mars 2006 à 15:30

Finding the stability number of a graph (A stable set is a subset of vertices in which any two are not adjacent and the stability number is the size of a maximum stable set.) is a well-studied problem in combinatorial optimization. It is NP-hard to compute and it is also difficult to approximate it. We propose an algorithm for computing a monotonic decreasing series of upper bounds for the stability number of a given graph. In every step of the series one has to solve a semidefinite programming problem. The algorithm is especially well-suited for highly symmetric graphs: By using harmonic analysis on finite groups one can (sometimes dramatically) reduce the size of the semidefinite programming problems. As a major example we consider the graph H(n,d). Its vertices are binary code words of length n and two vertices are adjacent if their Hamming distance is at most d - 1. Finding a maximum stable set in H(n,d) is equivalent to determining an optimal binary code of length n with minimum norm d. It turns out the the first step of our algorithm gives the classical linear programming bound due to Delsarte and that the second step gives the recent bound of Schrijver. This is joint work with Monique Laurent.