Polyhedral Techniques for the Design of Approximation Algorithms

本研究的目的是发展和完善一般技术，用于设计改进的近似算法，以解决困难的组合优化问题。这些问题出现在许多重要的应用领域，如电信或运输。重点将放在最具挑战性的问题上，这些问题在过去几十年里一直抵制着密集的研究。本研究计划使用和开发的一些工具来自多面体组合学，这是一个研究与组合优化结构相关的多面体的领域。线性规划方法在近似算法的设计和分析中得到了广泛的应用，但多面体组合学的全部功能尚未得到充分利用。最近在连通性问题上的显著进展突出了多面体技术的潜力。还有更多这样的联系有待发现，而这正是本研究的主要目标。

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.