AF: SMALL: Approximation Algorithms Matching Integrality Gaps for Network Design

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

Optimization problems that often arise in practice can be cast as those of designing appropriate networks that connect specified locations. Many such network design problems such as the traveling salesperson problem are computationally hard to solve exactly; nevertheless, approximation algorithms that run quickly yet deliver near-optimal solutions have been devised for solving them, often using these problems as exemplars to develop new techniques. A large set of these techniques for designing approximation algorithms are based on applying the mathematical modeling formalism of linear programming to obtain a starting point, and using different ways to convert them to actual solutions that are cheap. This project will study some prototypical network design problems under the linear programming formalism to establish the limits of its accuracy. In the process, the project will attempt to discover new techniques for designing such approximation algorithms, adding to the existing toolkit. Methods from the project will be useful in designing new stand-alone solutions for many network design problems as well as enhancing current methods that employ the linear programming framework. The project will synthesize diverse ideas from algorithm design, optimization theory and combinatorial discrete mathematics, and will broaden participation by supporting two female doctoral students. The educational plan will disseminate the results to a broad audience in Computer Science, Mathematics, Operations Research and Business where the PI is a professor. The set of problems examined in this project contains some of the long standing open problems in the theory of approximation algorithms, such as the symmetric traveling salesperson problem and its variants: the traveling salesperson path and two-edge-connected subgraph problems; it also includes other classical problems such as tree augmentation and prize-collecting Steiner forest that arise in a variety of network design applications. All these problems share the property that for their natural linear programming relaxations, the limits of these relaxations, also known as their integrality gaps, have not yet been established. The goal of the project is to design new approximation algorithms with performance ratios that match the exact integrality gap for these problems. These algorithms will be based on advancing current techniques such as primal-dual methods and iterated rounding, and developing new methods based on structural decompositions.