Optimization Online


Packing Ellipsoids with Overlap

Caroline Uhler (caroline.uhler***at***ist.ac.at)
Stephen Wright (swright***at***cs.wisc.edu)

Abstract: The problem of packing ellipsoids of different sizes and shapes into an ellipsoidal container so as to minimize a measure of overlap between ellipsoids is considered. A bilevel optimization formulation is given, together with an algorithm for the general case and a simpler algorithm for the special case in which all ellipsoids are in fact spheres. Convergence results are proved and computational experience is described and illustrated. The motivating application --- chromosome organization in the human cell nucleus --- is discussed briefly, and some illustrative results are presented.

Keywords: Ellipsoid Packing, Semidefinite Programming, Bilevel Optimization, Chromosome Organization

Category 1: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Category 2: Nonlinear Optimization (Constrained Nonlinear Optimization )

Category 3: Applications -- Science and Engineering (Biomedical Applications )

Citation: Technical Report, March, 2012. To appear in SIAM Review, 2013.

Download: [PDF]

Entry Submitted: 04/01/2012
Entry Accepted: 04/01/2012
Entry Last Modified: 02/10/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society