CAREER: Approximation Algorithms and Hardness of Network Optimization Problems

职业：网络优化问题的近似算法和难度

• 批准号: 0844872
• 负责人: Julia Chuzhoy
• 金额: $ 37.36万
• 依托单位: Toyota Technological Institute at Chicago
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-01-01 至 2013-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0844872&HistoricalAwards=false
• 关键词: CAREER; Approximation; Algorithms; Hardness; Network

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.

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