Approximation Algorithms for Network-Design and Transportation Problems

网络设计和运输问题的近似算法

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

This project is concerned with the development of practical algorithms for several network design problems, including problems related to graph connectivity.Another area studied is capacitated vehicle routing, which is closely related to the Traveling Salesman Problem. Given a collection of objects distributed at different locations, the problem is to deliver the objects to specified locations using a vehicle of bounded capacity. Such problems arise in transportation of goods and motion-planning of robots.

这个项目关注于几个网络设计问题的实用算法的发展，包括与图连通性相关的问题。另一个研究领域是有能力车辆路径，它与旅行商问题密切相关。给定一组分布在不同位置的对象，问题是使用有限容量的车辆将对象运送到指定位置。这些问题出现在货物运输和机器人的运动规划中。