The National Science Foundation (NSF) has awarded a research grant, in the expected amount of $800,000, to Philip Klein, Claire Mathieu and Ph.D. alum Glencora Borradaile (now Assistant Professor in the School of Electrical Engineering and Computer Science at Oregon State University), to develop new algorithms for solving fundamental optimization problems on planar networks. Many optimization problems in networks are considered computationally difficult; some are even difficult to solve approximately. However, problems often become easier when the input network is restricted to be planar, i.e., when it can be drawn on the plane so that no edges cross each other. Such planar instances of optimization problems arise in several application areas, including logistics and route planning in road maps, image processing and computer vision, and VLSI chip design.
The team plans to develop algorithms that achieve faster running times or better approximations by exploiting the planarity of the input networks. In addition, in order to address the use of optimization in the discovery of some ground truth, the investigators will develop algorithms not just for the traditional worst-case input model but also for models in which there is an unusually good planted solution; for a model of this kind, the investigators expect to find algorithms that produce even more accurate answers.
In addition, new algorithms and techniques resulting from this research might enable people to quickly compute better solutions to problems arising in diverse application areas such as computer vision. Further research has the potential to be useful, for example, in the design of networks, the planning of routes in road maps, and the processing of images.
