Center for Algorithms and Theory of Computation

CS 269S, Spring 2018: Theory Seminar
Bren Hall, Room 1423, 1pm


May 25, 2018:

Don’t Rock the Boat: Algorithms for Balanced Dynamic Loading and Unloading

Martha Osegueda, UCI

Consider dynamic loading and unloading problems for heavy one-dimensional geometric objects, in which we aim for balanced configurations at every step. We will discuss a variety of algorithms for computing balanced loading and unloading schemes minimizing the deviation from the center of gravity. Some of the results discussed are a 2.7 approximation to the NP-complete unloading problem and optimal approaches for 3 different loading scenarios.

Paper ( (https://arxiv.org/pdf/1712.06498.pdf) by Sándor P. Fekete, Sven von Hoveling, Joseph S. B. Mitchell, Christian Rieck, Christian Scheffer, Arne Schmidt, James R. Zuber