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 还将参加旨在鼓励女性更广泛地参与理论计算机科学的活动，包括参加以本科生和研究生为目标受众的研讨会和导师计划。