Bounding the density of packing objects: a symmetry-based optimization perspective

ACO Student Seminar
Friday, April 17, 2015 - 13:00
1 hour (actually 50 minutes)
Skiles 005
Georgia Tech
How much of space can be filled with pairwise non-overlapping copies of a given solid? This is one of the oldest problems in mathematics, intriguing since the times of Aristotle, and remaining remarkably elusive until present times. For example, the three-dimensional sphere packing problem (posed by Kepler in 1611) was only solved in 1998 by Ferguson and Hales. In this talk, I will provide some historical and modern applications of geometric packing problems, and I will introduce a methodology to derive upper bounds on the maximal density of such packings. These upper bounds are obtained by an infinite dimensional linear program, which is not computationally tractable. However, this problem can be approximated by using tools from sums of squares relaxations and symmetry reduction (harmonic analysis and representation theory), leading to rigorous computational upper bounds on the density. Time permitting, I will present ongoing work with Maria Dostert, Fernando de Oliveira Filho and Frank Vallentin on the density of translative packings of superspheres (i.e., ell_p balls). This is an introductory talk: no previous knowledge of sums of squares relaxations or symmetry reduction is assumed.