CAREER: Approximation Algorithms and Hardness of Network Optimization Problems

Toyota Technological Institute At Chicago, Chicago IL

Investigators

Abstract

CAREER: Approximation Algorithms and Hardness of Network Optimization Problems Julia Chuzhoy Network 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.