New techniques and directions in approximation algorithms

近似算法的新技术和方向

• 批准号: 386494-2010
• 负责人: Singh, Mohit
• 金额: $ 2.26万
• 依托单位: McGill University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2010
• 资助国家: 加拿大
• 起止时间: 2010-01-01 至 2011-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=463817
• 关键词: New; techniques; directions; approximation; algorithms

Combinatorial Optimization deals with obtaining efficient solutions to discrete problems. Most interesting combinatorial optimization problems, theoretical as well as practical, turn out to be NP-hard, and efficient algorithms which solve them exactly are not expected. One significant direction to solve these problems has been the field of approximation algorithms which computes bounds on the worst case performance of efficient heuristics. Despite significant progress over the years, several interesting and important problems remain open in the field. A primary focus of this proposal is to research new techniques for analyzing linear programming relaxations for the combinatorial optimization problems which will lead to new algorithms. In a related direction, this proposal will seek to apply the progress made on fundamental problems to real world problems in areas ranging from Airborne Network Topology Control, Wireless Mesh Networks to Multicasting in Wireless Networks.

组合优化处理离散问题的有效解决方案。大多数有趣的组合优化问题，无论是理论上的还是实际的，都是NP难的，并且不期望精确地解决它们的有效算法。解决这些问题的一个重要方向是近似算法领域，该算法计算有效算法的最坏情况性能的界限。尽管多年来取得了重大进展，但该领域仍存在一些令人感兴趣的重要问题。该建议的一个主要重点是研究分析线性规划松弛的组合优化问题，这将导致新的算法的新技术。 在相关的方向上，该提案将寻求将在基本问题上取得的进展应用于从机载网络拓扑控制、无线网状网络到无线网络中的多播的领域中的真实的世界问题。