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（称为sparsifier），该图大约保留了G相对于T的特性。一个人希望保留的特定类型的属性会产生几种类型的Sparsifier（例如，我们可能希望保留终端之间的corve cuts，流量或整体路由）。该领域的问题自然连接到近似算法（可以使用稀疏器来获得改进的近似因素到各种问题），固定参数的障碍性（在那里它们给出了一个黑色盒子来设计更快的算法），并且图形理论可以用图理论和图表进行了研究）。该领域仍然有许多开放问题，该项目将试图改善其中几个最新技术的状态。