Graph-theoretic Approximation Algorithms

图论近似算法摘要（nsf# 0105548）PI: Ramamoorthi Ravi，卡内基梅隆大学。随着通信信息网络规模的不断扩大，在低成本、高弹性网络设计中提出了一些新的问题；众所周知，就计算能力而言，要完全准确地解决这些问题，其中许多问题的成本高得令人望而却步。然而，这些问题抽象捕获了来自各种应用领域的模型，例如通信网络路由，大型网络中的多播消息，VLSI布局和具有规模经济的运输网络。本提案的研究旨在提高我们对这些涉及网络的固有棘手计算问题的良好解决方案结构的基础知识。研究人员将为这些问题开发近似算法——这些是启发式方法，以可量化的方式牺牲解决方案的准确性，以换取较低的计算资源。研究将涉及图论结果的应用和新发现，以指导这些启发式解决方案的设计。特别是，研究人员将设计具有改进性能比的多项式时间近似算法，用于许多基本图理论问题，包括增加树以使其成为双连接的问题，批量购买网络设计问题和最小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.