RIA: Approximation Algorithms for Hard Problems in Discrete Optimization
RIA: Approximation Algorithms for Hard Problems in Discrete Optimization
批准号:
9409625
负责人:
Balaji Raghavachari
金额:
$6.59万
依托单位国家:
美国
项目类别:
Continuing Grant
财政年份:
1994
资助国家:
美国
项目状态:
已结题
起止时间:
1994-09-01 至 1998-08-31
中文摘要
本研究的目的是开发新的算法技术,以有效地计算网络设计中出现的许多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.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
Approximation Algorithms for Network-Design and Transportation Problems
-
批准号:9820902
-
项目类别:Continuing Grant
-
资助金额:$16.49万
-
财政年份:1999
-
负责人:Balaji Raghavachari
-
依托单位:
海外基金