Solving and Approximating Combinatorial Optimization Problems (Towards MAX CUT and TSP)

摘要

We present a brief outline of recent development of combina-torial optimization. We concentrate on relaxation methods, on polyno-mial approximate results and on mutual relationship of various combina-torial optimization problems. We believe that this complex web of results and methods is typical for the modern combinatorial optimization. This paper is an introduction to our full paper [53].