RIA: Approximation Algorithms for Hard Problems in Discrete Optimization

本研究的目的是开发新的算法技术，以有效地计算近最优的解决方案，在网络设计中出现的一些NP-难图问题。 研究的部分问题包括：（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.