Changeset 1036:dff32ce3db71 in lemon-main for lemon/christofides_tsp.h

Timestamp:

01/09/11 15:06:55 (13 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

Make InsertionTsp? much faster and improve docs (#386)

File:

• lemon/christofides_tsp.h (modified) (1 diff)

lemon/christofides_tsp.h

@@ -41 +41 @@
   /// This a well-known approximation method for the TSP problem with
   /// metric cost function.
-  /// It yields a tour whose total cost is at most 3/2 of the optimum,
-  /// but it is usually much better.
+  /// It has a guaranteed approximation factor of 3/2 (i.e. it finds a tour
+  /// whose total cost is at most 3/2 of the optimum), but it usually
+  /// provides better solutions in practice.
   /// This implementation runs in O(n<sup>3</sup>log(n)) time.
   ///