CAREER: Approximation Algorithms and Hardness of Network Optimization Problems

职业生涯：网络优化问题的近似算法和难度Julia Chuzhoy网络优化问题在组合优化中扮演着核心角色，它们几乎出现在计算机科学的每个领域。由于许多这样的问题都是NP难的，一个自然的方法是解决产生接近最优或近似解的高效算法。在网络优化问题的背景下，已经发展了许多强大的算法范例和用于证明可逼近下界的技术，导致对这一类中的许多重要问题有了更好的理解。尽管取得了这些进展，但一些最基本的网络优化问题仍然知之甚少。这项研究将集中在图划分、图着色、网络设计和网络路由等领域的中心公开问题。本研究的目的之一是促进对这些问题的可近似性的理解。PI还希望探索算法设计和逼近证明的难易程度之间的联系，并结合在逼近算法、图论、逼近难易和概率可检验证明等领域开发的工具来探索网络优化问题的可逼近性。网络优化问题的更好的逼近算法将导致许多应用的性能提高，并且很可能需要开发新的算法范式。理解和隔离使问题变得棘手的特征将有助于在组合优化框架中为实际问题找到更好的公式，而这些特征是可以避免的。这个项目的教育部分包括介绍一门关于网络优化问题近似的新课程。该协会还将参加旨在鼓励妇女更广泛地参与理论计算机科学研究的活动。这些活动包括参加讲习班和辅导方案，其目标受众是高级本科生和研究生。

CAREER: Approximation Algorithms and Hardness of Network Optimization ProblemsJulia ChuzhoyNetwork optimization problems play a central role in combinatorial optimization, and they arise in virtually every area of computer science. Since many such problems are NP-hard, a natural approach is to settle for efficient algorithms that produce near-optimal, or approximate, solutions. Many powerful algorithmic paradigms, and techniques used in proving lower bounds on approximability, have been developed in the context of network optimization problems, leading to a better understanding of many important problems in this class. Despite this progress, some of the most fundamental network optimization problems remain poorly understood. This research will focus on central open problems in the areas of graph partitioning, graph coloring, network design and network routing. One goal of this research is to advance the understanding of the approximability of these problems. The PI would also like to explore the connections between algorithm design and hardness of approximation proofs, and to combine tools developed in the areas of approximation algorithms, graph theory, hardness of approximation and probabilistically checkable proofs in exploring the approximability of network optimization problems.Better approximation algorithms for network optimization problems will lead to improved performance for many applications, and will most probably require the development of new algorithmic paradigms. Understanding and isolating features that make problems intractable will help in finding better formulation for practical problems in the framework of combinatorial optimization, when such features can be avoided. The educational component of this project includes introducing a new course on approximation of network optimization problems. The PI will also participate in activities aimed at encouraging a broader involvement of women in research in theoretical computer science. These activities include participation in workshops and mentorship programs whose target audience is advanced undergraduate and graduate female students.