The aim of this research is to develop new algorithms and algorithmic techniques 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 investigators plan 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.
The research will likely uncover new computational techniques whose applicability goes beyond planar networks. In the recent past, once a technique has been developed and understood in the context of planar networks, it has been generalized to apply to broader families of networks.
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. For example, research in this area has already had an impact in the computer vision community. Further research has the potential to be useful, for example, in the design of networks, the planning of routes in road maps, the processing of images.
Planar instances of optimization problems arise in several application areas including designing delivery routes and selecting facility locations subject to road networks, telecommunication network design and VLSI chip design. An instance of an optimization problem is considered planar if an input to the problem is a graph that can be drawn such that no two edges cross. This project has developed several techniques for designing algorithms that are very efficient for planar inputs; that is, these algorithms perform much better than using techniques that work for general graphs. For example, we show how to find the maximum amount of flow (or information) that can be transmitted through the network and how to find the cheapest way to cut the graph so as to separate any given pair of vertices. These results and others have been made freely available on the site arXiv. Maximum flow and minimum cut problems as described above are often used in image segmentation problems. Early maximum flow results have been implemented and used in the computer vision community. Likewise we expect the results of this project to have implications in these fields that go beyond the auspices of theoretical computer science. The project has provided a training environment for many students including those from underrepresented populations; three female students and two Hispanic students have participated in this project. The PI (Borradaile) has written several posts on issues facing female researchers in this highly male-dominated field.
