AF: Small: Rounding by Sampling Method and Applications to Traveling Salesman Problems

AF：小：抽样方法舍入及其在旅行商问题中的应用

• 批准号: 1216698
• 负责人: Amin Saberi
• 金额: $ 50万
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-10-01 至 2017-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1216698&HistoricalAwards=false
• 关键词: AF; Small; Rounding; Sampling; Method

This project aims to further our understanding of the combinatorial structure of the Traveling Salesman Problem (TSP). It builds on a recent result that reduces asymmetric TSP to finding "thin trees'' in graphs and uses techniques in graph sparsification and metric embedding to develop new algorithms. It also includes the study of a new approximation algorithm for the symmetric TSP proposed by the project's Principal Investigator (PI) which is conjectured to break the 3/2 barrier due to Christofides. The project also advances the rounding-by-sampling method developed by the PI and co-authors, and extends it to design new algorithms for various online and stochastic problems. The proposed problems have applications in network design, online advertising, and power management in electrical networks.The proposed research on TSP has broad applications in logistics, planning, and vehicle routing. The other optimization problems studied in the project have applications ranging from online advertising to transmission and storage of alternative sources of energy. The project also includes a strong education and outreach component including the design of new courses on approximation algorithms and lectures on the subject for a broader audience.

本课题旨在加深我们对旅行推销员问题（TSP）的组合结构的理解。它建立在最近的一个结果的基础上，该结果将非对称TSP减少到寻找图中的“细树”，并使用图稀疏化和度量嵌入技术来开发新的算法。它还包括研究由该项目的首席研究员（PI）提出的对称TSP的新近似算法，该算法被推测可以打破由于Christofides造成的3/2障碍。该项目还推进了PI及其合著者开发的抽样舍入方法，并将其扩展到设计各种在线和随机问题的新算法。所提出的问题在网络设计、在线广告和电力网络中的电源管理中都有应用。提出的TSP研究在物流、规划、车辆路径等方面具有广泛的应用前景。该项目研究的其他优化问题的应用范围从在线广告到替代能源的传输和存储。该项目还包括一个强大的教育和推广组成部分，包括设计关于近似算法的新课程，并为更广泛的受众提供有关该主题的讲座。