New techniques and directions in approximation algorithms

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

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.