equal
deleted
inserted
replaced
38 /// ChristofidesTsp implements Christofides' heuristic for solving |
38 /// ChristofidesTsp implements Christofides' heuristic for solving |
39 /// symmetric \ref tsp "TSP". |
39 /// symmetric \ref tsp "TSP". |
40 /// |
40 /// |
41 /// This a well-known approximation method for the TSP problem with |
41 /// This a well-known approximation method for the TSP problem with |
42 /// metric cost function. |
42 /// metric cost function. |
43 /// It yields a tour whose total cost is at most 3/2 of the optimum, |
43 /// It has a guaranteed approximation factor of 3/2 (i.e. it finds a tour |
44 /// but it is usually much better. |
44 /// whose total cost is at most 3/2 of the optimum), but it usually |
|
45 /// provides better solutions in practice. |
45 /// This implementation runs in O(n<sup>3</sup>log(n)) time. |
46 /// This implementation runs in O(n<sup>3</sup>log(n)) time. |
46 /// |
47 /// |
47 /// The algorithm starts with a \ref spantree "minimum cost spanning tree" and |
48 /// The algorithm starts with a \ref spantree "minimum cost spanning tree" and |
48 /// finds a \ref MaxWeightedPerfectMatching "minimum cost perfect matching" |
49 /// finds a \ref MaxWeightedPerfectMatching "minimum cost perfect matching" |
49 /// in the subgraph induced by the nodes that have odd degree in the |
50 /// in the subgraph induced by the nodes that have odd degree in the |