| In this thesis,we consider the constrained maximum traveling salesman problem that is referred as the maximum traveling salesman problem with distances one and two,denoted by Max TSP{1,2}· The problem is defined as follows:Given a complete gragh G=（V,E;ω）,a weight function ω:E→｛1,2｝,it is asked to find a cycle C of maximum total edge weight,where C traverse each vertex exatly once.We design two polynomail-time approximation algorithms with worst-case ratios 8/9 and 11/12,respectively,to solve the constrained maximum traveling salesman problem with all distances one and two. |
