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.