Dividing a territory among multiple agents

John Gunnar Carlsson
Industrial and Systems Engineering
University of Minnesota, Minneapolis


Wednesday August 3, 2011
4:30 - 5:30 PM
Y2E2 105

Abstract:

In a wide variety of practical problems, a geographic region must be subdivided into smaller regions in a "fair" or "balanced" fashion. Region Partitioning, also called map segmentation or equitable subdivision, is the process of performing such divisions in an optimal way. Dividing a geographic region into smaller pieces is a problem that arises in many contexts, such as congressional redistricting ("gerrymandering") , logistics, and air traffic control. Often, some ways of dividing the region are better than others along one or several criteria. Partitioning a region is generally a difficult problem because the underlying optimization variables are infinite-dimensional and because shape constraints may be difficult to impose from within a standard optimization context. In this talk we present some new algorithms that solve several different classes of such problems.

---

Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html