Approximation Algorithms for Combinatorial Optimization Problems

本研究主要针对各种组合最佳化问题，设计有效的近似演算法。 主要目标是开发和隔离的一般技术，导致近似算法，以提高目前最好的性能保证几个组合优化问题，并开发这些算法的有效实现。 在过去几年中，在这些方面取得了重大进展;特别是基于原始-对偶方法的通用近似技术的发展，该方法导致了用于各种问题的第一和/或最佳近似算法，包括加权匹配问题，获奖旅行商问题，广义Steiner树问题和最一般版本的图扩充问题。 这项研究已经证明了线性规划技术在推导近似算法中的有用性。 线性规划是一个主要的工具，这是在这个项目中使用，以获得改进的近似算法。

This research is centered on the design of efficient approximation algorithms for a wide variety of combinatorial optimization problems. The main goal is to develop and isolate general techniques which lead to approximation algorithms, to improve the currently best performance guarantees for several combinatorial optimization problems and to develop efficient implementations for these algorithms. During the past few years substantial progress has been made in these directions; in particular, the development of a general approximation technique based on a primal-dual approach which lead to the first and/or best approximation algorithm for a variety of problems including the weighted matching problem, the prize-collecting traveling salesman problem, the generalized Steiner tree problem and the most general version of the graph augmentation problem. This research has demonstrated the usefulness of linear programming techniques in deriving approximation algorithms. Linear programming is one of the main tools that is to be used in this project in order to derive improved approximation algorithms.