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

这个项目将研究三大类优化问题：图路由，图绘制和顶点稀疏化。图路由问题通常针对连接具有不相交或几乎不相交路径的图顶点对。路由问题是组合优化的核心问题，在许多不同的应用中出现。 图形绘制的算法通过在平面中适当地绘制给定图形来帮助可视化给定图形。图稀疏因子允许我们用一个小得多的图来替换给定的图，从而保持原始图的路由属性。优化问题可以在较小的图上解决，从而获得更快的算法。本计画的目标是发展更好的近似演算法来解决图的路由与绘图问题，并建构更好更小的顶点稀疏化器。PI还将研究图划分问题，这些问题在图路由、绘图、稀疏化等领域的许多问题的算法设计中发挥着核心作用。图是最基本的组合对象之一，通常用于建模各种应用程序或表示数据。图划分、路由和绘制算法是处理图和解决图上优化问题的核心工具。为这些问题设计更好的近似算法将需要开发新的算法范例，这将很可能在近似算法领域及其他领域找到其他用途。PI研究的问题与其他领域有着有趣的联系，包括图子理论，固定参数可处理性和VLSI设计。该项目提供了与这些领域合作的机会，目标是将其多样化的技术工具和见解结合起来。这项研究为学生项目提供了广泛的机会，并将涉及来自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.