CRII: AF: New Approaches to Graph Spanners

Johns Hopkins University, Baltimore MD

Investigators

Abstract

This project is focused on research and educational activities related to graph spanners. In many applications it is important to "compress" distance information: if we are given pairwise distances between points, is there any way of storing them (possibly with some loss) other than storing all pairwise distances? This basic question, possibly with different definitions of "distances", arises in problems as diverse as property testing of mathematical functions, routing in computer networks, biomedical image segmentation, and many others. One standard way of doing this is through a graph spanner, in which we store only a small subset of the distances and then use those distances to (approximately) infer the ones that we did not store. Spanners have been studied extensively over the past 20 years, and we now have very good characterizations of what the tradeoffs are between the amount of information stored and the quality of the distance estimation. In this project the PI will take a different, more algorithmically-focused point of view: given points and distances, can we develop efficient algorithms that find the best possible spanner (or close to it)? The development of such algorithms would be a significant step forward from a theoretical point of view, as spanners seem to give mathematically difficult optimization problems. They are also related to many other problems in network design, and better algorithms for spanners will hopefully lead to better algorithms for a wide variety of related problems as well. Such algorithms would also be a step towards making spanners more practical, as they could be used to do "the best that we can" on any particular input, thus bypassing many of the known impossibility results which state only that some inputs cannot be compressed. This project also has a significant educational component. The PI will develop and refine classes on algorithms for distance spaces and approximation algorithms. The PI will also supervise research projects related to this project performed by undergraduates from Johns Hopkins and from other institutions. Finally, the PI will work with talented high school students in Baltimore on appropriate projects. More formally, graph spanners are subgraphs which preserve distances, and are a basic algorithmic building block that is used widely throughout theoretical computer science. The vast majority of research on spanners has been in the form of existential questions. For example, what types of spanners exist? What are sufficient conditions or necessary conditions to achieve certain parameters? What tradeoffs between various parameters are possible? While these are all extremely interesting questions, the related optimization questions have received much less attention. For example, if we are given a graph, is there an efficient algorithm to find the best (or close-to-best) spanner? This and other related questions move graph spanners from the realm of graph theory into the realm of algorithms. In this project the PI will study these optimization problems through the lens of approximation algorithms. More specifically, in this project the PI will extend the existing linear programming-based techniques and develop new techniques based on other convex relaxations in order to design approximation algorithms for graph spanners. These algorithms will be based on relaxation-based techniques (in particular the Sherali-Adam LP hierarchy and the Lasserre SDP hierarchy). In parallel to this, the PI will design improved lower bounds including both hardness results (through novel reductions from 2-player 1-round proof systems) and integrality gaps for convex relaxations.