AF: Small: Approximation Algorithms for Graph and Combinatorial Optimization Problems

University Of Illinois At Urbana-Champaign, Urbana IL

Investigators

Abstract

Graphs and combinatorial optimization problems are central to algorithmic development, and have numerous applications in computer science and beyond. Many natural problems in these two areas are NP-Hard and approximation algorithms have been a very successful approach to address this intractability. In addition to providing algorithms and heuristics, approximation is a useful lens to examine the structure of NP-Hard problems. Despite the enormous progress made in the area of approximation algorithms and hardness of approximation, several basic and fundamental problems still remain wide open. This project will examine several interrelated problems from four broad areas. Our main tools will be linear and mathematical programming methods coupled with graph theoretic ideas. The problem areas of interest are: (i) Multiflow and routing problems such as maximum disjoint paths, congestion minimization and flow-cut gaps. The central goal is to understand the relationship between fractional multiflows, integer multiflows and cuts both in the throughput and concurrent flow settings. (ii) Network design, in particular obtaining a poly-logarithmic approximation for the directed Steiner tree problem, and approximability of variants of the survivable network design problem. (iii) Traveling salesman problem (TSP), orienteering and related tour and walk problems in directed graphs. (iv) Submodular function maximization subject to constraints and applications. The proposed research is at the intersection of algorithms, classical combinatorial optimization, mathematical programming, and graph theory. The technical work serves to exchange ideas between these areas and it is expected that it will lead to new algorithms and heuristics for fundamental problems. These problems arise in many applications in computer science (in particular network problems), operations research, and engineering; these would benefit from the algorithmic advances. The project will train two PhD students and a manuscript on algorithms and applications of submodular function maximization is expected to be produced.