Monday, November 20, 2006
Technische Universität Berlin
Straße des 17. Juni 136
Math building - Room MA 041
Lecture - 14:15
In geometry, the kissing number problem asks for the maximum number k(n) of unit spheres that can simultaneously touch the unit sphere in n-dimensional Euclidean space without overlapping. It is trivial that k(1) = 2, k(2) = 6, and the question whether k(3) = 12 or k(3) = 13 was the subject of a famous discussion between Issac Newton and David Gregory in 1694. This question was finally solved only in 1953 by Schuette and van der Waerden. Today the kissing number is only known for n = 1, 2, 3, 4, 8, 24, where the k(4) = 24 was proved by O. Musin in 2003.
In this lecture I will explain a general method based on semidefinite programming to find upper bounds for packing problems of this kind. This method is a strengthening of the linear programming method which P. Delsarte developed in the seventies and it as an adaption of A. Schrijver's approach who derived new upper bounds for binary codes using semidefinite programming.
We implemented this approach and we found computationally, but rigorously, new upper bounds for k(n) in several dimensions. In particular we found a unified proof for all cases when the kissing number is known.
This is joint work with Christine Bachoc. See also the preprints "New upper bounds for kissing numbers from semidefinite programming" (http://arxiv.org/abs/math.MG/0608426) and "Semidefinite programming, multivariate orthogonal polynomials, and codes in spherical caps" (http://arxiv.org/abs/math.MG/0610856).
Colloquium - 16:00
Many natural IP-formulations bear symmmetries, as they allow for a large group to act on the variables such that the objective function remains constant along every orbit of the feasible solutions. This causes severe problems for state-of-the art IP solvers due to unnecessarily large branch-and-bound trees and extremely poor LP relaxation bounds. In this talk we will discuss polyhedra (called orbitopes) that are associated with well-known ways to remove symmetries from IP- formulations by addition of inequalities that cut off large parts of each of the orbits (while leaving at least one solution feasible in each orbit). In particular, we will provide complete and irredundant inequality descriptions of the convex hull of the 0/1- matrices that have exactly one one-entry per row and whose colums are in lexicographically decreasing order, as well as of the convex hull of all 0/1-matrices with two columns the first of which is lexicographically not larger than the second one. The talk is based on joint work with Marc E. Pfetsch (ZIB) and Andreas Loos (TU Berlin).