Approximation Algorithms for Network Design Problems
(L. C. Lau)

Network design is a central topic in combinatorial optimization, approximation algorithms, and operations research. The basic setting of network design problems is to find a minimum cost subgraph satisfying connectivity requirements between vertices. This captures a number of classical combinatorial optimization problems, such as minimum cost flow, Hamiltonian cycle and minimum Steiner tree. Furthermore, research results in this area provide algorithmic tools and insights for the design of practical networks such as telecommunication networks.

Motivated by the practical applications, there is a growing need for more sophisticated and realistic models for the design of practical networks. One important topic is degree-bounded network design problems, where the objective is to find a minimum cost subgraph satisfying connectivity requirements as well as degree bounds (e.g. workloads) on the vertices. Using the iterative relaxation method, we have obtained additive approximation algorithms for a large class of degree bounded network design problems, in which the maximum degree of the solutions is at most an additive constant more than the maximum degree of the optimal solutions. This adds to a rather small list of problems that an additive approximation algorithm is known. Unfortunately, these algorithms are based on solving linear programming relaxations of the problems, and are not efficient in practice. One objective of this project is to develop efficient and purely combinatorial approximation algorithms for these problems, which would have significant practical value to the design of communication networks. Another objective of this project is to obtain new algorithmic results for other interesting network design problems. Recently, we have obtained some encouraging results in network design problems with metric costs, and we will continue to pursue new directions in this area.