Graph-theoretic Approximation Algorithms

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

Abstract for GRAPH-THEORETIC APPROXIMATION ALGORITHMS (NSF #0105548) PI: Ramamoorthi Ravi, Carnegie Mellon University. The increasing size of communication and information networks has motivated several new problems in the design of networks with low cost and high resilience; Many of these problems are known to be prohibitively expensive in terms of computing power to solve to full accuracy. Yet these problem abstractions capture models from a variety of application areas such as communication network routing, multicasting messages in large networks, VLSI layout, and transportation networks with economies of scale. The research in this proposal aims to advance our fundamental knowledge of the structure of good solutions to such inherently intractable computational problems involving networks. The investigators will develop approximation algorithms for these problems -- these are heuristic methods that trade off some accuracy in the solution in return for lowered computational resources, in a quantifiable way. The research will involve the application of and new discovery of results in the theory of graphs to guide the design of these heuristic solutions. In particular, the investigators will design polynomial-time approximation algorithms with improved performance ratios for many basic graph-theoretic problems including the problem of augmenting a tree to make it two-connected, buy-at-bulk network design problems and the minimum $k$-cut problem. The investigators will continue their ongoing study of bicriteria network design problems (problems that involve two objective functions to be optimized simultaneously) to design improved bicriteria approximation algorithms for many spanning tree problems arising in practice; These problems involve a combination of commonly studied objectives such as the maximum node degree, diameter and total cost of the tree. The research effort will focus on the theme of studying natural mathematical programming formulations for these NP-hard problems and attempt to derive improved approximation guarantees via rounding algorithms that will also establish the integrality gap of these basic formulations.