New techniques and directions in 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.