308-360 Tutorial #8

1. Apply both TSP heuristics, the 2-approximation algorithm, the spanning tree bound, the nearest neighbor bound, and the 1-tree bound to the following distance matrix. How close to optimum is the best tour?

This problem and its 2-approximation algorithm are found on page 969 of CLR.

Heuristic: A rule of thumb, a simple rule or approach that will help to find a good solution, though not provably an optimal solution. For instance, a heuristic that you probably already use is that when finding a vertex cover, it makes sense to choose vertices of maximal degree.

Lower Bound: A lower bound k of a problem states that no valid solution to that problem can have a better score/value than k. Note that an algorithm to find a lower bound is not an algorithm to find the nearest to optimal solution. It provides information about the set of possible solutions.

The length of any TSP tour >= any TSP lower bound.

The relationship of the bounds and solutions attained using the algorithms mentioned in this question can be understood by the following statements:

4. 1-tree lower bound ( weight(T*) + D[x1,y] + D[x1,z] where T* = MST for a tour S - x1, and y and z are the two nearest vertices to x1 )
>= 5. Spanning Tree lower bound ( weight(T*) where T* = MST for G )

1. and 2. Length of TSP tour found using heuristic methods (NN or Shortest Link)
>= Length of the optimal tour
>= Any of the Lower Bounds 4., 5., 6.

2 x length of the optimal tour
>= 3. Length of TSP tour found using the 2 approximation algorithm (walk & triangle inequality algorithm)
>= Length of the optimal tour
>= Any of the Lower Bounds 4., 5., 6.


Algorithms to find a Tour

1. Tour Found Using Nearest-Neighbour Heuristic
T = AC + CD + DE + EF + FB + BA = 21.

2. Tour Found Using Shortest Link Heuristic
T = AC + CD + DE + AB + BF + EF = 21.

3. Tour Found Using 2-Approximation Algorithm Using Walk & Triangle Inequality
Walk = ABACDEFEDCA. Preorder Walk = ABCDEF. T = AB + BC + CD + DE + EF + FA = 25.

Algorithms to find a Lower Bound

4. 1-Tree Lower Bound
Find a MST for the graph without vertex A. An example is a MST with the following edges: CB, CD, DE, DF. The MST weight is 12. The 1-tree lower bound is 12 + AC + AB = 19.

5. Spanning Tree Lower Bound
Find a mimimal spanning tree and add up the weights of the edges. An example tree has the following edges: AB, AC, CD, DF, DE with a total weight of 16. So the spanning tree lower bound is 16.

6. Nearest-Neighbour Lower Bound
Use arbitrary tour A,C,D,E,F,B,A.
Add up the NN distances. i.e. NN to A is C, NN to F is D. NN-LowerBound = AC + CA + DC + ED + FD + BA = 3 + 3 + 3 + 3 + 3 + 4 = 19.

2. Give a linear programming formulation for Independent Set.

The A Matrix
The A matrix represents the input graph G. A is an m x n matrix such that A(j,i) = 1 if vertex i is an endpoint of edge j and 0 otherwise.

The X Vector
The X vector is the variable vector representing the members of the maximal independent set of G. Since each X entry corresponds to one vertex and there are n vertices, there are n X entries. So X is an n-vector. If X(i) = 1 then vertex i is a member of the independent set. If X(i) = 0, then vertex i is not a member of the independent set.

The Corresponding Maximal Independent Set
The size of the independent set S is therefore the number of vertices that are members of S. It follows that |S| = sum(X(i)) for all i in X.

The Linear Programming Objective
The linear program will maximize the object function. We want the linear program to find the largest independent set S, so to maximize the number of vertices that are members of S. So, the objective function to maximize is the sum(X(i)) for all xi in X.

The Linear Programming Constraint
By definition, any two vertices in an independent set must not be adjacent. So, if vi and vj are both in the independent set, there can not be an edge between vi and vj. For every i,j for which (vi, vj) is an edge, X(i) + X(j) < 2. This means that either X(i) or X(j) can be set to 1, but not both. Which is the same as saying that since (vi,vj) is an edge, only one of its endpoints can be a member of the independent set S.

In linear programming notation, this becomes:
sum( A(j,i)X(i) ) < 2, for all j. Note that the constraint m-vector b = 2.

The Linear Programming Solution
The linear program will find the X vector that satisfies these constraints and provides the maximal value to the objective function. Example (use the A matrix in the figure above)
Invalid X = [ 1 1 0 0 0 ]:

The previous X vector is invalid because both a and b cannot be in the independent set, as they are adjacent vertices in G. Note that in class you wrote these vectors vertically, but because of html, I'm not. The constraint specified above therefore would not hold because at j = 1, sum( A(j,i)X(i) ) = 1x1 + 1x1 + 0x0 + 0x0 + 0x0 = 2.

Solution X = [ 1 0 0 1 1 ]:

A possible solution to the X vector is X = [ 1 0 0 1 1 ]. This corresponds to S = { a, d, e }. Verify the the contraint holds with this X vector and that the objective function is maximized.