September 17, 2012, ESB 2001

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, and show how they may be applied to various applications in vehicle routing and facility location.

John Gunnar Carlsson is an assistant professor in the Department of Industrial and Systems Engineering at the University of Minnesota.  He received a Ph.D. in computational mathematics from ICME in Stanford University in 2009 and an AB in mathematics and music from Harvard College in 2005.  His primary research interests involve applications of analytical tools from computational geometry, mathematical optimization, and geometric probability theory to problems in transportation and location science, such as vehicle routing, network design, and facility location.  He is the recipient of a 2012 DARPA Young Faculty Award and the 2010 INFORMS Interactive Session Prize.  His research is supported by DARPA, the Office of Naval Research, the National Science Foundation, the Minnesota Department of Transportation (MnDOT), and the Boeing Company.