# Combinatorial Optimization - Cristofides N.

**Download**(direct link)

**:**

**44**> 45 46 47 48 49 50 .. 156 >> Next

Another NP-complete problem with similar properties in ste. In the euclidean case where auxiliary vertices may be placed everywhere in the

The Complexity of Combinatorial Optimization Algorithms

121

wt <wo *V h "c

WT <3/2 *0

Figure 5.3 T, shortest spanning tree; M matching of odd degree vertices in T; w0, weight of optimum tour; wh, weight of heuristically obtained tour

Figure 5.4

122

Francesco Maffioli

plane, a strongly supported conjecture (Gilbert and Pollack, 1968) states that the ratio between the optimum tree and a spanning tree without auxiliary vertices is never less than V3/2, while a lower bound of 1/J3 has been proved in Graham and Huang (1976). In Hwang (1976) the rectilinear metric Steiner problem is considered and the spanning tree without auxiliary vertices is shown to be no more than 50% longer than the minimum length rectilinear Steiner tree.

Algorithms for placement or allocation problems have been analysed in Chandra and Wong (1975), Karp, McKellar, and Wong (1975), and Comue-jols, Fisher, and Nemhauser (1975). Some of these heuristics have very good worst case behaviour. For instance, the two-dimensional placement problem of Karp, McKellar, and Wong (1975) is shown to be always solvable within an additive constant of optimum (most of other results mentioned so far are within multiplicative constant optimum).

5.7 Probabilistic Heuristic Evaluation

The fact that computational experience shows many heuristics to work quite well even if their worst case behaviour is quite bad has recently encouraged researchers to pay increasing attention to methods which can be proved to work well on the average. Unfortunately it is very difficult, if not impossible, in most cases to know the real probability distribution of the various problem instances.

What is normally done therefore is to assume a certain probability distribution and derive a result which we hope will depend very little from this assumption.

Some definitions from probability theory (Feller, 1968) concerning problem distributions are given here.

Let S, be the sample space of problems of size i and x a random sample from -n-(x) a property of x. Then

Pi = Prob {-7r(x) holds} = 1 - fli Definition 5.1 We say that n holds almost everywhere if

X 9i<-

i = l

Definition 5.2 We say that 7r holds with probability which tends to one if

lim Pi = 1.

Let us remark that the second definition establishes a weaker requirement than the first and that we are looking for asymptotic properties in both cases.

The Complexity of Combinatorial Optimization Algorithms

123

The main reference for this section is the work of Karp (1976) and again some of the more interesting results are obtained for the euclidean travelling salesman problem.

Let in fact Tn be a random variable equal to the length of a shortest tour through n points given completely at random inside a region of the plane of area A. The following results hold (Beardwood, Halton, and Hammersley, 1959):

(A) Tn^yJ(An) (y a constant),

(B) there exists a constant /3 such that, for all e > 0

(3-?<^-</3 + 6 (5.1)

V(nA)

almost everywhere.

Result (A) establishes a worst case behaviour, while result (B) establishes an average behaviour. Experiments tend to indicate a value of /3 of about 0.75.

For convenience let now A = 1 be the area of a unit square of the plane and consider the following heuristic, assuming that problems of size ^Sf may be solved optimally by our computer sufficiently quickly.

Step 1 Subdivide A into smaller regions A,, each one containing n, of the given points, until tij ^ t for all i, by the technique of Figure 5.5, i.e. dividing A into rectangles obtained always by a segment parallel to the smaller side.

Figure 5.5

124

Francesco Maffioli

Step 2 Construct shortest tours for each region Af.

Step 3 Treat each subtour as a point and construct a minimum spanning tree connecting them all.

Step 4 Obtain an eulerian tour taking the small tours and twice each tree edge.

Step 5 Eliminate pairs of edges from the eulerian tour in order to get a hamiltonian tour of smaller length (see Figure 5.6).

Let now c, be the cost of the ith subtour, c0 the cost of the optimum tour, and ch the dost of the tour obtained by the algorithm. The following results are reported in Karp (1976).

Theorem 5.3 (Worst case) There exist constants a, and a2 such that

The Complexity of Combinatorial Optimization Algorithms

125

Corollary 5.1 ch c0=S(aL + a2)

Theorem 5.4 (Average case) There exists a 5 such that

ch-c0*s8

almost everywhere.

Algorithms based on similar partitioning principles and with similar properties apply to Steiner tree problems as well as to the same problems in other metric or in spaces of higher dimensionality.

For a different density function f(x, y) governing the distribution of the points into the unit square, if

a similar result applies since now instead of (5.1) we have (Beardwood, Halton, and Hammersley, 1959)

A completely different kind of approach, due to Posa (1976), may be applied to the so-called Bottleneck Travelling Salesman Problem, i.e. the problem of finding a hamiltonian tour in a given arc-weighted graph such that the length of its longest arc is minimized. The approach is based upon the theory of random graphs.

**44**> 45 46 47 48 49 50 .. 156 >> Next