CAREER: Approximation Algorithms and Hardness of Network Optimization Problems

职业：网络优化问题在组合优化中起着核心作用，它们几乎出现在计算机科学的每个领域。由于许多这样的问题是NP难的，一个自然的方法是解决有效的算法，产生近最佳，或近似，解决方案。许多强大的算法范例和用于证明逼近性下界的技术都是在网络优化问题的背景下开发的，从而使人们更好地理解本课程中的许多重要问题。尽管取得了这些进展，但一些最基本的网络优化问题仍然知之甚少。这项研究将集中在中心开放的问题，在该地区的图划分，图着色，网络设计和网络路由。本研究的一个目标是推进对这些问题的可逼近性的理解。PI还希望探索算法设计与近似证明难度之间的联系，并将近似算法、图论、近似硬度和概率可检查证明领域开发的联合收割机工具结合起来，探索网络优化问题的近似性。更好的网络优化问题近似算法将提高许多应用程序的性能，并且很可能需要开发新的算法范例。理解和隔离的功能，使问题棘手的将有助于在组合优化的框架中找到更好的制定实际问题，当这样的功能可以避免。该项目的教育部分包括介绍网络优化问题近似的新课程。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.