Packing ellipsoids with overlap

Abstract:

Problems of packing shapes with maximal density, sometimes into a container of restricted size, are classical in  discrete mathematics. We describe here the problem of packing a given set of ellipsoids of different sizes into a finite container, in a way that allows overlap but that minimizes the maximum overlap between adjacent ellipsoids. We describe a bilevel optimization algorithm for finding local solutions of this problem, both the general case and the easier

special case in which the ellipsoids are spheres. Tools from conic optimization, especially semidefinite programming, are key to the algorithm.  Finally, we describe the motivating application - chromosome arrangement in cell nuclei - and compare the computational results obtained with this approach to experimental observations.

This talk represents joint work with Caroline Uhler (IST Vienna)