The Maximum Traveling Salesman Problem With Distances One And Two

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.