Approximation Algorithms for Combinatorial Optimization Problems

点击翻译按钮获取中文摘要

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.