Graph-theoretic Approximation Algorithms

点击翻译按钮获取中文摘要

Abstract for GRAPH-THEORETIC APPROXIMATION ALGORITHMS (NSF #0105548)PI: Ramamoorthi Ravi, Carnegie Mellon University.The increasing size of communication and information networks has motivatedseveral new problems in the design of networks with low cost and highresilience; Many of these problems are known to be prohibitively expensivein terms of computing power to solve to full accuracy. Yet these problemabstractions capture models from a variety of application areas such ascommunication network routing, multicasting messages in largenetworks, VLSI layout, and transportation networks with economies of scale.The research in this proposal aims to advance our fundamental knowledge ofthe structure of good solutions to such inherently intractable computationalproblems involving networks. The investigators will develop approximationalgorithms for these problems -- these are heuristic methods that trade offsome accuracy in the solution in return for lowered computational resources,in a quantifiable way. The research will involve the application of and newdiscovery of results in the theory of graphs to guide the design of theseheuristic solutions.In particular, the investigators will design polynomial-time approximationalgorithms with improved performance ratios for many basic graph-theoreticproblems including the problem of augmenting a tree to make ittwo-connected, buy-at-bulk network design problems and the minimum $k$-cutproblem. The investigators will continue their ongoing study of bicriterianetwork design problems (problems that involve two objective functions to beoptimized simultaneously) to design improved bicriteria approximationalgorithms for many spanning tree problems arising in practice; Theseproblems involve a combination of commonly studied objectives such as themaximum node degree, diameter and total cost of the tree. The researcheffort will focus on the theme of studying natural mathematical programmingformulations for these NP-hard problems and attempt to derive improvedapproximation guarantees via rounding algorithms that will also establishthe integrality gap of these basic formulations.