The weekly SILO Seminar Series is made possible through the generous support of the 3M Company and its Advanced Technology Group


with additional support from the Analytics Group of the Northwestern Mutual Life Insurance Company

Northwestern Mutual

Packing Ellipsoids and Chromosomes

Stephen Wright, Professor, Computer Sciences

Date and Time: Sep 12, 2012 (12:30 PM)
Location: Orchard room (3280) at the Wisconsin Institute for Discovery Building


Problems of packing shapes with maximal density, possibly into a
container of restricted size, are classical in discrete
mathematics. We describe here the problem of packing ellipsoids of
given (but varying) dimensions into a finite container, in a way that
minimizes the maximum overlap between adjacent ellipsoids. A bilevel
optimization algorithm is described for finding local solutions,
for both the general case and the easier special case in
which the ellipsoids are spheres. Algorithm and analysis tools
from semidefinite programming and trust-region methods are key to the
approach. We apply the method to the problem of chromosome arrangement in cell
nuclei, and compare our results with the experimental observations
reported in the biological literature. (Joint work with Caroline Uhler, IST Austria)