AF: Small: Graph Routing, Vertex Sparsifiers, and Connections to Graph Theory

AF：小：图路由、顶点稀疏器以及与图论的连接

基本信息

批准号：
1616584
负责人：
Julia Chuzhoy
金额：
$ 44.97万
依托单位：
Toyota Technological Institute at Chicago
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2016
资助国家：
美国
起止时间：
2016-09-01 至 2020-08-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1616584&HistoricalAwards=false
关键词：
AF Small Graph Routing Vertex

项目摘要

Graphs are basic combinatorial objects that are widely used in computer science, engineering, and beyond. Many problems, both theoretical and practical, can be abstracted through graphs, and graphs are also used to represent data. Several basic optimization problems on graphs naturally arise in many different contexts, and it is important to build and expand a toolkit of algorithmic ideas and techniques for addressing such problems. This project will focus on two broad classes of graph optimization problems: graph routing and graph sparsification. Graph routing problems are used as abstractions in many applications, for example, when designing VLSI chips, in multi-robot motion planning, and routing traffic across optical networks. Graph sparsification can be a useful tool in analyzing large and complex networks, including social ones, and in designing faster algorithms for a variety of graph problems. Graph routing and sparsification problems were studied in several different areas, such as approximation algorithms, fixed parameter tractability, and graph theory. In addition to designing better algorithms for such problems, another goal of the project is to increase the flow of ideas and collaboration between these different communities, by studying problems lying in the intersection of these areas. The project will involve graduate and possibly undergraduate students from TTIC and University of Chicago, as well as students from other institutions who participate in TTIC's summer internship program. The PI will also participate in activities aimed at increasing the participation of women in theoretical computer science.Typically in a graph routing problem one is given a graph G and a collection of pairs of vertices, called demand pairs, that need to be connected to each other. The goal is to connect as many of the pairs as possible via paths, usually subject to some restrictions on the maximum load on graph vertices or edges. These are fundamental problems that have been studied extensively by both theoretical computer science and graph theory communities. Unfortunately, there are still wide gaps in our understanding of some of the most basic problems in this area, and this project aims to make progress on them. In graph sparsification problems, one is given a graph G and a small set T of its vertices called terminals. The goal is to represent the graph G by a much smaller graph H (called a sparsifier), that approximately preserves the properties of G with respect to T. The specific types of properties one would like to preserve give rise to several types of sparsifiers (for example, we may want to preserve cuts, flows or integral routings between the terminals). Problems in this area naturally connect to approximation algorithms (where sparsifiers can be used to obtain improved approximation factors to various problems), fixed-parameter tractability (where they give a black-box way to design faster algortihms), and to graph theory (many sparsification problems can be cast in graph theoretic terms and have been studied by the graph theory community). There are still many open problems in this area, and this project will attempt to improve the state of the art on several of them.

图是基本的组合对象，广泛应用于计算机科学、工程等领域。很多问题，无论是理论还是实践，都可以通过图来抽象，图也用来表示数据。图上的几个基本优化问题自然会在许多不同的环境中出现，构建和扩展用于解决此类问题的算法思想和技术工具包非常重要。该项目将重点关注两大类图优化问题：图路由和图稀疏化。图路由问题在许多应用中被用作抽象，例如，设计 VLSI 芯片、多机器人运动规划以及跨光网络路由流量时。图稀疏化可以成为分析大型复杂网络（包括社交网络）以及为各种图问题设计更快算法的有用工具。图路由和稀疏化问题在多个不同领域进行了研究，例如近似算法、固定参数易处理性和图论。除了为此类问题设计更好的算法之外，该项目的另一个目标是通过研究这些领域交叉点中的问题来增加这些不同社区之间的思想流动和协作。该项目将涉及 TTIC 和芝加哥大学的研究生和可能的本科生，以及参加 TTIC 暑期实习计划的其他机构的学生。 PI 还将参加旨在增加女性参与理论计算机科学的活动。通常，在图路由问题中，会给出一个图 G 和一组顶点对（称为需求对）的集合，这些顶点对需要连接到每个顶点对。其他。目标是通过路径连接尽可能多的对，通常会受到图顶点或边上最大负载的一些限制。这些是理论计算机科学和图论社区广泛研究的基本问题。不幸的是，我们对这一领域一些最基本问题的理解仍然存在很大差距，而这个项目旨在在这些问题上取得进展。在图稀疏化问题中，给定一个图 G 和它的一小部分顶点集 T（称为终端）。目标是用一个更小的图 H（称为稀疏器）来表示图 G，该图大致保留 G 相对于 T 的属性。人们想要保留的特定类型的属性会产生几种类型的稀疏器（例如，我们可能希望保留航站楼之间的剪切、流动或整体路由）。该领域的问题自然与近似算法（其中稀疏器可用于获得各种问题的改进近似因子）、固定参数易处理性（其中它们提供了设计更快算法的黑盒方法）以及图论（许多稀疏化问题可以用图论术语来表达，并且已被图论界研究过）。该领域仍然存在许多未解决的问题，该项目将尝试提高其中几个问题的最新技术水平。