Planarity-exploiting algorithms for optimization problems
<-- Return to the list
Date: 11-25-2008
Start Time:
1:00pm
End Time: 2:00pm
Speaker: Philip Klein, Computer Science Department: Brown University
Location: 303 Mudd
ABSTRACT
In the past few years, substantial progress has been made on algorithms for some classical optimization problems in planar graphs. For polynomial-time problems such as directed max-flow and shortest paths, more efficient algorithms have been obtained. For NP-hard problems such as Steiner tree and TSP, fast approximation schemes have been discovered. We survey the state of the art and examine some of the common techniques underlying these developments.
BIO
Philip Klein is Professor of Computer Science at Brown University. He earned a B.A. in Applied Mathematics at Harvard and a Ph.D. in Computer Science from MIT. In 1991, he received Presidential Young Investigator Award. In 2007, he received Brown's Philip J. Bray award for Teaching Excellence in the Physical Sciences.