Monday, November 20, 2006
Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin
Math building - Room MA 041
room 005
Lecture - 14:15
Abstract:
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
Abstract:
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).