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 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.

T = AC + CD + DE + EF + FB + BA = 21.

T = AC + CD + DE + AB + BF + EF = 21.

Walk = ABACDEFEDCA. Preorder Walk = ABCDEF. T = AB + BC + CD + DE + EF + FA = 25.

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.

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.

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.