AF: Small: Algorithms for Graph Routing, Drawing and Partitioning

AF：小型：图形路由、绘图和分区算法

• 批准号: 1318242
• 负责人: Julia Chuzhoy
• 金额: $ 46.41万
• 依托单位: Toyota Technological Institute at Chicago
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-01-01 至 2017-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1318242&HistoricalAwards=false
• 关键词: AF; Small; Algorithms; Graph; Routing

This project will study three broad families of optimization problems: graph routing, graph drawing, and vertex sparsification. Graph routing problems typically aim at connecting pairs of graph vertices with disjoint or nearly disjoint paths. Routing problems are central to combinatorial optimization, and arise in many different applications. Algorithms for graph drawing assist with visualizing a given graph, by appropriately drawing it in the plane. Graph sparsifiers allow us to replace a given graph by a much smaller one, that preserves the routing properties of the original graph. Optimization problems can then be solved on the smaller graph, thus obtaining faster algorithms. This project aims at developing better approximation algorithms for graph routing and drawing problems, and constructing better and smaller vertex sparsifiers. The PI will also study graph partitioning problems, that play a central role in designing algorithms for many problems in the areas of graph routing, drawing, sparsification, and beyond.Graphs are among the most basic combinatorial objects, and are often used to model various applications, or to represent data. Algorithms for graph partitioning, routing and drawing are central tools for manipulating graphs and solving optimization problems on them. Designing better approximation algorithms for such problems will require developing new algorithmic paradigms, that will most likely find other uses across the field of approximation algorithms and beyond. The problems the PI studies have interesting connections to other areas, including Graph Minor Theory, Fixed Parameter Tractability, and VLSI Design. This project presents an opportunity for collaboration with these areas, with the goal of combining their diverse technical tools and insights. This research offers a broad range of opportunities for student projects, and will involve graduate 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 encouraging a broader involvement of women in theoretical computer science, including participation in workshops and mentorship programs whose target audience is undergraduate and graduate female students.

这个项目将研究三大类优化问题：图路由、图绘制和顶点稀疏。图的布线问题通常以连接具有不相交或几乎不相交的路径的图顶点对为目标。路由问题是组合优化的核心问题，存在于许多不同的应用领域。图形绘制算法通过在平面上适当地绘制图形来帮助可视化给定的图形。图稀疏器允许我们用一个小得多的图替换给定的图，从而保留了原始图的路由属性。然后可以在较小的图上解决优化问题，从而获得更快的算法。该项目的目的是开发更好的近似算法来解决图的布线和绘制问题，并构造更好和更小的顶点稀疏器。PI还将研究图划分问题，图划分问题在为图的布线、绘制、稀疏等领域的许多问题设计算法时发挥着核心作用。图是最基本的组合对象之一，通常用于对各种应用程序进行建模，或表示数据。图的划分、布线和绘制算法是处理图和解决图上的优化问题的核心工具。为这类问题设计更好的近似算法将需要开发新的算法范例，这很可能会在近似算法领域乃至更远的领域找到其他用途。PI研究的问题与其他领域有有趣的联系，包括图子理论、固定参数可处理性和VLSI设计。这个项目提供了一个与这些领域合作的机会，目的是将他们的各种技术工具和见解结合起来。这项研究为学生项目提供了广泛的机会，将包括来自TTIC和芝加哥大学的研究生，以及参加TTIC暑期实习计划的其他机构的学生。PI还将参加旨在鼓励妇女更广泛地参与理论计算机科学的活动，包括参加以本科生和研究生为目标受众的讲习班和辅导方案。