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

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

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.