CAREER: New Mathematical Programming Techniques in Approximation and Online Algorithms

Regents Of The University Of Michigan - Ann Arbor, Ann Arbor MI

Investigators

Abstract

Numerous applications in engineering, science and business are modeled and solved as combinatorial optimization problems. In today?s digital age, data collection and storage is inexpensive. The bottleneck lies in society's ability to solve increasingly larger problem instances, where the challenge typically stems from computational or informational limitations. This intractability can often be overcome by searching for approximately optimal instead of exactly optimal solutions. This project will design new mathematical-programming-based techniques that are broadly applicable in approximating combinatorial optimization problems. The project will strengthen connections of theoretical computer science to various fields of mathematics such as discrepancy theory, geometry, graph theory, optimization and probability. The PI will also collaborate with industry colleagues to disseminate the theoretical findings on some of the studied problems and assess their practical impact. The educational aspect of this project includes training undergraduate and graduate students, developing new course material and organizing a workshop for high-school teachers. Despite the wide range of possible combinatorial optimization problems, a common approach underlying numerous results in approximation and online algorithms is mathematical programming and rounding. This project will develop new techniques in this area by investigating (1) algorithms based on convex-programming hierarchies, (2) rounding algorithms based on recent advances in algorithmic discrepancy and (3) an online primal-dual framework for convex objectives. This project involves designing general algorithmic techniques (and identifying problem classes to which they apply) as well as improving the state-of-art on central problems such as k-Median, directed Steiner tree, the Beck-Fiala conjecture, unsplittable flow and online multicommodity routing. This project will also expand the applicability of the resulting techniques to areas such as combinatorics and operations research.