Speakers

Christine Bachoc (University of Bordeaux)

Henry Cohn (Microsoft Research New England)

Christoph Helmberg (Technical University of Chemnitz)

Etienne de Klerk (Tilburg University)

Rekha Thomas (University of Washington)

Program

10h00-10h30 Welcome and coffee

10h30-11h15 Christine Bachoc

11h30-12h15 Etienne de Klerk

12h30-14h00 lunch break

14h00-14h45 Rekha Thomas

15h00-15h45 Christoph Helmberg

16h00-16h45 Henry Cohn

When and where?

Friday, March 13, 2009

CWI Amsterdam,

Eulerzaal

Where is it?

Organizers

Monique Laurent (CWI Amsterdam), Frank Vallentin (CWI Amsterdam)

Participants

Karen Aardal (TU Delft), Alireza Asadi (TU Delft), Hartwig Bosse (U Frankfurt), Jop Briet (CWI Amsterdam), Peter Csorba (TU Eindhoven), Edwin van Dam (U Tilburg), Cristian Dobre (U Tilburg), Jan Draisma (TU Eindhoven), Mirjam Duer (U Groningen), Christian Eggermont (TU Eindhoven), Murat Firat (TU Eindhoven), Dion Gijswijt (UvA and CWI Amsterdam), Joao Gouveia (U Washington), Guoyong Gu (TU Delft), Willem Haemers (U Tilburg), Gunnar Klau (CWI Amsterdam), Goran Lesaja (Georgie Southern U), Monique Laurent (CWI Amsterdam), Bertrand Meyer (CWI Amsterdam and U Bordeaux), Fernando Oliveira Filho (CWI Amsterdam),  Rudi Pendavingh (TU Eindhoven), Farzenah Ramezani (TU Amirkabir), Cordian Riener (U Frankfurt), Cees Roos (TU Delft), Alexander Schrijver (CWI Amsterdam), Bib Paruhum Silalahi (TU Delft), Renata Sotirov (U Tilburg), Dimitri Sverdlov (TU Delft), Elias Tsigaridas (INRIA Sophia Antipolis), Frank Vallentin (CWI Amsterdam)

Abstracts and Presentations

New applications of semidefinite programming to coding theory

Christine Bachoc

A classical problem in coding theory asks for the maximal number of elements of a binary code with given minimal Hamming distance. This question can be seen as an optimization problem where the constraint concerns pairs of elements of a code. It turns out that several applications to information theory lead to coding theoretic problems which express in terms of the k-tuples of elements of a code. It is the case for cryptographic applications leading to the notion of generalized Hamming distance, or in the context of list-decoding. We shall discuss these notions and show how the recent SDP method introduced by A. Schrijver can be applied to derive bounds in these situations.

Linear and semidefinite programming bounds in discrete geometry

Henry Cohn

Linear and semidefinite programming bounds are the most powerful known techniques for studying packing and coding problems.  For reasons nobody has yet been able to understand, linear programming bounds are far more powerful than they have any right to be, while semidefinite programming bounds, which seem in principle to be much more powerful, have led to only modest improvements overall.  In this talk, I'll discuss what we do and don't know about these bounds and why they are so perplexing.

Graph Realizations Corresponding to Optimized Extremal Eigenvalues of the Laplacian

Christoph Helmberg

joint work with Susanna Dienelt, Frank Göring, Markus Wappler

In spectral graph partitioning heuristics the initial partition is typically based on the sign structure of the Fiedler vector, i.e, the eigenvector to the second smallest eigenvalue of the Laplace matrix of the graph. In order to obtain a better understanding of connections between the spectrum of the Laplacian and separator structures in the graph we study graph realizations in Euclidean space obtained from the optimal solutions of semidefinite programs that seek to optimize the extremal eigenvalues of the Laplacian by redistributing the mass on the edges of the graph. We show that not only the geometric structure of optimal graph realizations is tightly linked to the separator structure of the graph but that in both cases (maximizing the second eigenvalue and minimizing the largest eigenvalue) there even exist optimal realizations whose dimension is bounded by the tree width of the graph plus one. In case of maximizing the second eigenvalue, introducing node weights and edge lengths and maximizing the minimum dimension of optimal realizations over all possible node weights and edge lengths gives rise to a  minor monotone graph parameter, the rotational dimension of the graph. We give a forbidden minor characterization for graphs of dimension 0, 1, and 2.

On semidefinite programming relaxations of the traveling salesman problem

Etienne de Klerk

joint work with Cristian Dobre, Renata Sotirov, Dmitrii V. Pasechnik

We consider a new semidefinite programming (SDP) relaxation of the symmetric traveling salesman problem (TSP), that may be obtained via an earlier SDP relaxation (Q. Zhao, S.E. Karisch, F. Rendl, H. Wolkowicz, 1998) of the more general quadratic assignment problem (QAP).  We show that the new relaxation dominates the one by Cvetković et al. 1999. Unlike the bound of Cvetković et al., the new SDP bound is not dominated by the Held-Karp (G.B. Dantzig, D.R. Fulkerson, S.M. Johnson, 1954 and Held, Karp 1970) linear programming bound, or vice versa. The new SDP bound has an interpretation in terms of the association scheme of the optimal tour.

Extending Lovász's Theta Body of a Graph to all Real Varieties

Rekha Thomas

joint work with Joao Gouveia, Pablo Parrilo

The theta body of a graph, constructed by Lovász about 30 years ago, is one of the first examples of SDP approximation in discrete optimization. This body has a not-so-well-known definition in terms of sums of squares polynomials that appears in papers by Lovász in the 1990s. Using this definition and a question he raises, we define a hierarchy of theta bodies for any real algebraic variety (real solutions to a polynomial system over the reals). We prove that these theta bodies are SDP relaxations of the convex hull of real varieties and are in fact a version of Lasserre's relaxations. For the max cut problem this hierarchy appears to be new. When the real variety is finite (as is usual in combinatorial optimization), we give a complete characterization of when the first theta body in the hierarchy equals the convex hull of the variety.

Additional lectures on related topics

We also organize additional lectures (by Elias Tsigaridas, Jop Briet, Joao Gouveia, Bertrand Meyer) on related topics on Wednesday, March 11 and Thursday, March 12.