Notes and Comments:

• Chapter 1, p.49: 'While empirically, local minima of basically any instance of a combinatorial optimisation problem can be found reasonably fast, theoretically, in most cases the number of steps needed by an iterative improvement algorithm to find a local optimum cannot be bounded by a polynomial.'

  Comment: Results for special cases exist; for example, 2-opt local search for the TSP is expected to require a polynomial number of steps (to be precise: O(n¹⁰ log n)) to find a local minimum in the worst-case for any Euclidean TSP instance [Chandra et al., 1999]. Other work on this subject is referenced in Chandra et al. [1999].

• Chapter 4, p.154: 'For optimisation LVAs, the concepts of completeness, probabilistic approximate completeness and essential incompleteness can be applied to the associated decision problems in a straightforward way, using the following generalisations:'

  Comment: The formalisation in Definition 4.4 is based on the assumption that the given optimisation problem is stated as a minimisation problem (as stated on p.16, this assumption is made, without loss of generality, throughout the book).

• Chapter 5, p.241f., Figures 5.9 and 5.10

  Comment: The dotted lines are exactly those edges with weight < 0.01 that are required to make the partial PCGs connected; there are other edges of weight < 0.01 between the nodes of these partial PCGs that are not shown.

[Back to SLS Book Home Page]