this is by minimum weight matching using algorithms of . Making a graph into an Eulerian graph starts with the minimum spanning tree. Then all the vertices of odd order must be made even. So a matching for the odd degree vertices must be added which increases the order of every odd degree vertex by one. This leaves us with a graph where every vertex is of even order which is thus Eulerian. Adapting the above method gives the algorithm of Christofides and Serdyukov. Find a minimum spanning tree for the problem Create a matching for the problem with the set of cities of odd order. Find an Eulerian tour for this graph Convert to TSP using shortcuts. Pairwise exchange The pairwise exchange or 2-opt technique involves iteratively removing two edges and replacing these with two different edges that reconnect the fragments created by edge removal into a new and shorter tour. Similarly, the 3-opt technique removes 3 edges and reconnects them to form a shorter tour. These are special cases of the k-opt method. The label Lin–Kernighan is an often heard misnomer for 2-opt. Lin–Kernighan is actually the more general k-opt method. For Euclidean instances, 2-opt heuristics give on average solutions that are about 5% better than Christofides' algorithm. If we start with an initial solution made with a greedy algorithm, the average number of moves greatly decreases again and is . For random starts however, the average number of moves is . However whilst in order this is a small increase in size, the initial number of moves for small problems is 10 times as big for a random start compared to one made from a greedy heuristic. This is because such 2-opt heuristics exploit 'bad' parts of a solution such as crossings. These types of heuristics are often used within Vehicle routing problem heuristics to reoptimize route solutions. k-opt heuristic, or Lin–Kernighan heuristics The Lin–Kernighan heuristic is a special case of the V-opt or variable-opt technique. It involves the following steps: Given a tour, delete k mutually disjoint edges. Reassemble the remaining fragments into a tour, leaving no disjoint subtours (that is, don't connect a fragment's endpoints together). This in effect simplifies the TSP under consideration into a much simpler problem. Each fragment endpoint can be connected to other possibilities: of 2k total fragment endpoints available, the two endpoints of the fragment under consideration are disallowed. Such