Polyhedral Techniques for the Design of Approximation Algorithms

Massachusetts Institute Of Technology, Cambridge MA

Investigators

Abstract

The aim of this research is to develop and refine general techniques for the design of improved approximation algorithms for hard combinatorial optimization problems. Such problems arise in many important application areas such as telecommunications or transportation. The focus will be on the most challenging problems that have resisted intense research for the last few decades. Some of the tools that this research plans on both using and developing come from polyhedral combinatorics, an area concerned with the study of polyhedra related to combinatorial optimization structures. Linear programming approaches have been much used in the design and analysis of approximation algorithms, but the full power of polyhedral combinatorics has not been exploited yet. Remarkable recent progress on connectivity problems highlights the potential of polyhedral techniques. Many more such connections are waiting to be discovered, and this is precisely the main goal of this research.