Philip Klein has been awarded a $300,000 grant from the National Science Foundation. The funding will support Klein's research on algorithms for solving optimization problems on planar graphs - graphs that can be drawn on the plane with no crossings. Such graphs are necessary in image processing and road map logistics.
Possible uses for planar graphs research are illustrated by the following scenario - imagine a truck driver who must develop the shortest possible route to supply vending machines at numerous locations. This scenario is a version of the infamous Traveling Salesman Problem; and finding the shortest route that visits all required locations is considered a computationally intractable problem.
Klein's prior work implies that because a road map is essentially a planar graph, for any percentage error tolerance ε >0 desired, there is an O(n log n) algorithm to find a route whose length is at most 1+ε times that of the shortest. The grant will support Klein's continuing efforts to discover and mathematically analyze algorithms of this kind. Visit rhodemap.org for more information.
The Theoretical Foundations Program received approximately five hundred proposals, of which 15% received support.
