Graph-theoretic Approximation Algorithms

摘要图论近似算法（NSF#0105548）PI：Ramamoorthi Ravi，卡内基梅隆大学通信和信息网络的规模不断扩大，在低成本和高弹性的网络设计中产生了一些新问题;众所周知，这些问题中的许多问题在计算能力方面都非常昂贵，无法完全准确地解决。然而，这些问题的抽象捕获模型从各种应用领域，如通信网络路由，在largenetworks，超大规模集成电路布局，和交通网络的规模经济，在这个建议的研究旨在推进我们的基础知识的结构，良好的解决方案，这种固有的棘手的计算问题，涉及网络。 研究人员将为这些问题开发近似算法--这些是启发式方法，以量化的方式，在解决方案中牺牲一些准确性，以换取更低的计算资源。研究将涉及图论中的应用和新发现的结果，以指导这些启发式解决方案的设计。特别是，研究人员将设计多项式时间近似算法，提高性能比的许多基本图论问题，包括问题的扩大一棵树，使它成为两个连接，购买批量网络设计问题和最小$k$-割问题。研究人员将继续他们正在进行的双准则网络设计问题（涉及两个目标函数同时优化的问题）的研究，以设计改进的双准则近似算法来解决实践中出现的许多生成树问题;这些问题涉及到通常研究的目标，如树的最大节点度，直径和总成本的组合。研究工作将集中在研究自然的数学规划公式为这些NP难问题的主题，并试图通过舍入算法，也将建立这些基本公式的完整性差距，以获得改进的近似保证。

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.