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.
The project focused on the development of approximation algorithms for combinatorial optimization problems on graphs and submodular functions. Many of these problems are intractable to solve exactly under standard complexity theoretic assumptions. Approximation algorithms are heuristics that run efficiently and output solutions that have a guarantee on their sub-optimality. The design and analysisof these algorithms provide a principled way to develop heuristics and also unravel the structural properties of the underlying problems.The project succeeded in developing new and improved approximationalgorithms for several fundamental problems. Some key results are outlined below. Constrained submodular function optimization: We developed a general framework based on mathematical programming for maximizing and minimizing submodular set functions under a variety of constraints. The framework is based on solving a continuous extension of a submodular function followed by suitable rounding. This has led to the substantially improved approximation algorithms for several problems. Our algorithmic ideas have found applications in machine learning. Routing problems: We developed algorithms for a basic routing problem called the maximum disjoint paths problem. Here the goal is to connect as many given source-sink pairs as possible in a network via paths that do not share edges or nodes. We obtained new algorithms for two cases. The first is for node disjoint paths in general undirected graphs, and the second is for edge disjoint paths in graphs with small treewidth. Network design: We developed improved algorithms for the survivable network design problem and its prize-collecting version when the cost of the network is on both the edges and nodes of the network. The project supported three PhD students who have finished their dissertations and are faculty members in Computer Science Departments. The project also supported the writing of a manuscript onalgorithms for submodular function maximization which is nearingcompletion.
