Design and Analysis of Algorithms - New Paradigms, Methodologies and Applications

算法的设计和分析——新范式、方法论和应用

• 批准号: 0515221
• 负责人: Michel Goemans
• 金额: $ 20万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-08-01 至 2008-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0515221&HistoricalAwards=false
• 关键词: Design; Analysis; Algorithms; New; Paradigms

Many optimization problems that arise in various industries, including logistics, production planning, transportation and telecommunication, have to be solved repeatedly and in automated fashion. In many cases, the underlying mathematical optimization problem is provably hard, and cannot be solved to optimality in a reasonable amount of time. As a result, the task of the algorithm designer is to develop algorithms that are efficient and provide good solutions on every single run, as a far from optimum solution even just once might be catastrophic, either in terms of the cost of the solution obtained or in terms of its inability to meet demands or other constraints. This stresses the importance of designing efficient algorithms for hard combinatorial optimization problems that deliver solutions guaranteed to be probably close to the optimum. This area of approximation algorithms has seen a tremendous growth in the last decade, with a host of new results. The intellectual merit of this proposal is to develop new methodologies and techniques to provide the algorithm designer with the tools to design approximation algorithms and is also to focus on crucial problems. These problems include fundamental problems such as the traveling salesman problem and other network problems which arise as building blocks in many industrial settings. A special emphasis will be given to settings in which the data evolves over time and the algorithm's task is to provide a constantly changing solution to meet the fluctuating requirements. This solution needs to be robust against these fluctuations, and remain close to optimum at any time.The broader impact of this proposal is to provide industry with the tools to bemore productive and more efficiently use the available resources, and this in turn will have an impact on the economy. The proposal also seeks funds for the training of graduate students and this is important to maintain the competitively of our workforce and guarantee the best possible training for the next generation of faculty members teaching on our college campuses.

各个行业（包括物流、生产计划、运输和电信）中出现的许多优化问题必须以自动化的方式重复解决。在许多情况下，潜在的数学优化问题被证明是困难的，并且无法在合理的时间内解决最优问题。因此，算法设计者的任务是开发高效的算法，并在每次运行时提供良好的解决方案，因为即使只有一次，远非最佳的解决方案也可能是灾难性的，无论是在获得解决方案的成本方面，还是在其无法满足需求或其他约束方面。这强调了为硬组合优化问题设计有效算法的重要性，这些算法提供的解决方案保证可能接近最优。近似算法这一领域在过去十年中取得了巨大的发展，并产生了大量新成果。该提案的智力价值在于开发新的方法和技术，为算法设计者提供设计近似算法的工具，并且重点关注关键问题。这些问题包括基本问题，例如旅行推销员问题和其他网络问题，这些问题在许多工业环境中作为构建块出现。将特别强调数据随时间变化的设置，算法的任务是提供不断变化的解决方案以满足不断变化的需求。该解决方案需要能够抵御这些波动，并随时保持接近最佳状态。该提案的更广泛影响是为行业提供提高生产力和更有效地利用可用资源的工具，这反过来将对经济产生影响。该提案还为研究生培训寻求资金，这对于保持我们劳动力的竞争力并保证为在我们大学校园教学的下一代教职人员提供最好的培训非常重要。