RIA: Approximation Algorithms for Hard Problems in Discrete Optimization

这项研究的目的是开发新的算法技术来有效地计算网络设计中出现的一些NP-Hard图问题的近最优解。所研究的部分问题包括：(A)欧几里得环境下的问题，包括旅行商问题；(B)为多种商品流设计低拥塞网络；(C)计算广播树以在网络中快速传播信息；(D)寻找具有指定连通性的低成本网络。我们的目标是开发出不仅能产生好的解，而且在实际中可行的算法。开发的算法都得到了实现和测试。

The objective of this research is to develop new algorithmic techniques to compute efficiently near optimal solutions to a number of NP-hard graph problems arising in network-design. A partial list of problems studied include: (a) problems in Euclidean setting including the traveling salesman problem; (b) designing low-congestion networks for multicommodity flow; (c) computing broadcast-trees for fast dissemination of information in networks; (d) finding low-cost networks of specified connectivity. The goal is to develop algorithms which not only generate good solutions, but are also practically feasible. Algorithms developed are both implemented and tested.