RIA: Approximation Algorithms for Hard Problems in Discrete Optimization

RIA：离散优化中难题的近似算法

• 批准号: 9409625
• 负责人: Balaji Raghavachari
• 金额: $ 6.59万
• 依托单位: University of Texas at Dallas
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1994
• 资助国家: 美国
• 起止时间: 1994-09-01 至 1998-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9409625&HistoricalAwards=false
• 关键词: RIA; Approximation; Algorithms; Hard; Problems

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.

本研究的目的是开发新的算法技术，以有效地计算近最优的解决方案，在网络设计中出现的一些NP-难图问题。 研究的部分问题包括：（a）欧几里德设置的问题，包括旅行推销员问题;（B）设计低拥塞网络的多商品流;（c）计算广播树的快速传播的信息在网络中;（d）找到低成本的网络指定的连通性。我们的目标是开发算法，不仅产生良好的解决方案，但也实际可行。 算法开发的实施和测试。