RIA: Efficient Algorithms for Computational Graph Theory

计算图论已经成为发展算法技术(例如，动态算法、在线算法、并行算法、近似算法、数据结构设计等)的强大媒介。图论为交通运输、网络设计、优化、超大规模集成电路等许多领域提供了一种很好的建模方法。这使得人们可以开发和说明不同算法工具的强大功能。本课题研究高效算法设计的两个方面。第一个方面是研究难以解决的问题(许多优化问题都属于这一类)，并设计有效的算法来获得近似解。第二个方面是研究那些已知在多项式时间内完全可解的问题，但已知的上下界之间有很大的差距。所研究的具体问题是在设计高效可靠的通信网络时变得越来越重要的问题。它们解决了与以低成本实现更高可靠性通信相关的问题，并且与网络设计和广播协议的实施有关。在这些问题的解决方案中使用的一些工具和想法也将应用于解决其他问题。

Computational graph theory has emerged as a powerful medium for the development of algorithmic techniques (e.g., for dynamic algorithms, on-line algorithms, parallel algorithms, approximation algorithms, data structure design, etc.). Graph theory provides an excellent way to model problems related to transportation, network design, optimization, VLSI and many other fields. This allows one to both develop and illustrate the power of different algorithmic tools. This project studies two aspects of efficient algorithm design. The first aspect is the study of intractable problems (many optimization problems fall under this category), and the design of efficient algorithms to obtain approximate solutions. The second aspect is the study of problems that are known to be solvable exactly in polynomial time, but there is a wide gap between the known upper and lower bounds. The specific problems studied are problems that are becoming important in the design of efficient and reliable communication networks. They address issues that are relevant for higher reliability of communication at low cost, and are of interest in network design and in the implementation of broadcast protocols. Some of the tools and ideas that are used in the solutions for these problems will have applications to solving other problems as well.