Events & News
Colloquium
| Category | Lecture |
| Date | Thursday, February 9, 2012 |
| Time | 11:00 am |
| Concludes | 12:00 pm |
| Location | Gould-Simpson 906 |
| Speaker | Aparna Das |
| Affiliation | University of Arizona |
Designing Algorithms for Euclidean Routing Problems
Optimization problems involving path planning and scheduling abound in computer science, from the planning of transportation and robot surveillance routes, to the design of communication networks, to scheduling jobs efficiently on a machine. Unfortunately many of these problems are NP-Hard, so we are unlikely to find efficient and optimal algorithms to solve them. One approach is to design efficient approximation algorithms which guarantee solutions that are close to the optimal solution.
The optimization problems mentioned above are well formulated as graph problems and in many practical settings we can also assume that distances in the graph are determined by Euclidean distances. In this talk we show how to obtain stronger approximation guarantees (getting closer to the optimal solution) by exploiting Euclidean properties in the underlying graph. To get good solutions we use geometric decomposition techniques to dissect the graph into small pieces and solve each piece separately. We demonstrate how this technique is used to obtain better approximation guarantees for the Euclidean Vehicle Routing problem and the Minimum Manhattan Network problem in low dimensional Euclidean space.
Note: This is a practice job talk and I would really appreciate any feedback the audience can provide.
Biography
Aparna completed her Phd from Brown University in 2011 and is currently a post-doc at the University of Arizona.
Her research interests include the design and analysis of algorithms, geometric algorithms, combinatorial optimization, and computational game theory.