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.
Many combinatorial optimization problems arising in areas such as telecommunication and transportation are provably hard to solve to optimality. This is for example the case for the infamous traveling salesman problem (TSP) of finding the best route to visit a set of locations so as to minimize the distance traveled. This project has introduced new techniques and algorithms for the design and analysis of approximation algorithms which deliver solutions with an a priori guarantee on the level of suboptimality and whose running times grow slowly with the size of the problem (eg the number of cities to be visited). A major success in this project is with regard to the Asymmetric Traveling Salesman Problem (ATSP). This is a variant of the TSP in which the distance from A to B might be different from the distance from B to A. We have designed an algorithm for ATSP with the best known performance guarantee and this has introduced novel ideas and techniques on how to tackle this challenging problem. It is likely that these ideas will eventually result in better, practical algorithms for ATSP. Another important success of this project is for the Steiner tree problem, which consists of finding the cheapest of connecting a set of locations (eg offices, or computers) in a (telecommunication) network. For this problem, we have also obtained an algorithm with best known performance guarantee and have higlighted connections with matroid theory that are essential for the improved efficiency and analysis. Many other results were obtained under this project, including a study of the size required for extended formulations of combinatorial optimization problems. The project has had broader impacts. Two graduate students and two postdoctoral fellows trained as part of this project have contributed much to its success and are now well equipped to conduct their own research. All four of them are now starting their academic careers as junior faculty members in major universities. Some of the results and ideas obtained in this project have informed the development of educational material both at the undergraduate and graduate level.
