CRII: AF: New Approaches to Graph Spanners

该项目侧重于与图形扳手相关的研究和教育活动。在许多应用程序中，“压缩”距离信息是很重要的：如果我们被给予点之间的成对距离，除了存储所有成对距离之外，有没有其他方法来存储它们(可能会有一些损失)？这个基本的问题，可能有不同的距离定义，出现在各种各样的问题中，如数学函数的性质测试，计算机网络中的路由，生物医学图像分割，以及许多其他问题。一种标准的方法是通过图形扳手，在其中我们只存储距离的一小部分，然后使用这些距离来(大约)推断我们没有存储的距离。在过去的20年里，扳手得到了广泛的研究，我们现在已经很好地描述了存储的信息量和距离估计的质量之间的权衡。在这个项目中，PI将采取一种不同的、更注重算法的观点：给定点和距离，我们能否开发出找到(或接近)最佳可能扳手的高效算法？从理论角度来看，这种算法的开发将是一个重大的进步，因为扳手似乎给出了数学上困难的优化问题。它们还与网络设计中的许多其他问题有关，对于扳手来说，更好的算法也有望导致更好的算法来解决各种相关问题。这样的算法也将是使扳手变得更实用的一步，因为它们可以用来对任何特定的输入“尽我们所能”，从而绕过许多已知的不可能结果，这些结果只表明某些输入无法压缩。这个项目也有一个重要的教育组成部分。PI将开发和改进距离空间和近似算法的算法课程。PI还将监督约翰·霍普金斯大学和其他机构的本科生进行的与该项目有关的研究项目。最后，PI将与巴尔的摩有才华的高中生一起进行适当的项目。更正式地说，图形扳手是保持距离的子图，是在整个理论计算机科学中广泛使用的基本算法构件。绝大多数关于扳手的研究都是以存在主义问题的形式进行的。例如，存在哪些类型的扳手？达到某些参数的充分条件或必要条件是什么？各种参数之间可能有什么权衡？虽然这些都是非常有趣的问题，但相关的优化问题却没有得到太多关注。例如，如果给我们一张图，有没有一种有效的算法来找到最好的(或接近最好的)扳手？这个问题和其他相关问题将图形处理程序从图论领域转移到算法领域。在这个项目中，PI将通过近似算法的镜头来研究这些优化问题。更具体地说，在这个项目中，PI将扩展现有的基于线性规划的技术，并开发基于其他凸松弛的新技术，以便为图处理程序设计近似算法。这些算法将基于基于松弛的技术(特别是Sherali-Adam LP层次结构和Lasserre SDP层次结构)。同时，PI将设计改进的下界，包括硬度结果(通过从2人1轮证明系统的新减少)和凸松弛的完整性间隙。

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.