Final Exam, Spring 2001

Take Home Due: 5pm, Monday, 30 April, 2001.

This is to be all your own work. You may use any result from class, homeworks, or the books and papers on reserve in the library. Do not consult anybody or anything else. I can dispense hints to help you if you are stuck. My office extension is 276-6915 and you can also reach me by email at mitchj@rpi.edu. I will have office hours Wednesday from 1-3pm and Friday 2-4pm. The exam consists of four questions and is worth 100 points.

In order that I can display grades, please write a 4 digit number on the front of your solution set.

- 1.
- (25 points)
Consider a bipartite graph
*G*=(*V*,*E*), where*V*can be broken into two parts*U*and*W*, and every edge in*E*has one endpoint in*U*and one in*W*. (Formally, , , and implies that*e*=(*i*,*j*), where and .) Note that we have not assumed that every vertex in*U*is adjacent to every vertex in*W*. Because this is a bipartite graph, the maximum cardinality matching problem can be solved by solving its linear programming relaxation

where*x*_{ij}is one if edge (*i*,*j*) is in the matching, and zero otherwise. Every basic feasible solution to both (*P*) and its dual (*D*) is integral.- (a)
- (5 points)
What is the dual (
*D*) to the linear program (*P*)? (Hint: The dual of a linear program of the form is .) - (b)
- (10 points)
A
*node cover*of*G*is a subset*S*of*V*such that every edge in*E*is incident to at least one vertex in*S*. What do the integral solutions to (*D*) correspond to? What do you conclude from strong duality? - (c)
- (10 points)
What are the complementary slackness conditions for the
pair (
*P*) and (*D*)? Interpret these conditions.

- 2.
- (20 points)
- (a)
- (10 points)
Let
*M*=(*N*,*F*) be a matroid defined on the finite set*N*and with independent sets*F*. The**dual matroid**to*M*can be defined as the independence system on the finite set*N*with its maximal independent sets equal to the complements of the maximal independent sets in*M*. Show that is a matroid. (Note: The dual matroid is defined in a different way in Nemhauser and Wolsey. I want you to use the definition I've given you here to prove this result, and not to use the definition in the text.) - (b)
- (10 points)
A
*matric matroid**M*_{1}=(*N*_{1},*F*_{1}) can be represented using a matrix: elements of the finite set*N*_{1}correspond to columns of the matrix, and the independent sets in*F*_{1}correspond to linearly independent subsets of the columns. A*graphic matroid**M*_{2}=(*N*_{2},*F*_{2}) can be represented using a graph: elements of the finite set*N*_{2}correspond to edges of the graph, and the independent sets in*F*_{2}correspond to acyclic subsets of the edges. Show that any graphic matroid is also a matric matroid.

- 3.
- (30+10 points) Let
*G*be a complete graph on 2*s*vertices, for some integer . Let each edge*e*have weight*c*_{e}. The*equipartition problem*on this graph is to divide the vertices into two sets of size*s*so as to minimize the sum of the weights of the edges that have one endpoint in each set. One polyhedral representation of this problem requires defining variables

for each edge*e*.- (a)
- (5 points) Show that
*x*must satisfy the equality for each vertex*v*, where denotes the set of edges incident to vertex*v*. - (b)
- (5 points)
Show that the dimension of the feasible region is no more than

- (c)
- (Extra credit: 10 points)
Show that the dimension of the feasible region is exactly

- (d)
- (5 points) Let
*C*be a cycle of length 3 and let*E*(*C*) denote the edges of this cycle. Show that any feasible solution satisfies

- (e)
- (5 points) Let
*C*be a cycle of length*s*+1 and let*E*(*C*) denote the edges of this cycle. Show that any feasible solution satisfies

- (f)
- (10 points)
Solve the instance of the equipartition problem contained in
http://www.rpi.edu/~mitchj/matp6620/final/equi.mod

andhttp://www.rpi.edu/~mitchj/matp6620/final/equi8.dat

using a cutting plane method.

- 4.
- (25 points)
Another approach to the equipartition problem is to define a variable

where*k*takes the values 1 and 2, corresponding to the two sides of the equipartition. Let*g*^{(p)}denote the*p*-vector with every entry equal to one.- (a)
- (8 points)
Let
*W*denote the 2 x 2*s*matrix whose (*k*,*j*)th entry is*w*_{kj}. Show that the entries of*W*satisfy*Wg*^{(2s)}=*sg*^{(2)}and*W*^{T}*g*^{(2)}=*g*^{(2s)}. - (b)
- (8 points)
Let
*X*denote the 2*s*x 2*s*matrix whose (*i*,*j*)th entry is the variable*x*_{ij}defined in Question 3 corresponding to the edge*e*=(*i*,*j*). Show that*E*-*X*=*W*^{T}*W*for any feasible equipartition, where*E*denotes a matrix whose every entry is one. - (c)
- (9 points)
Show that an SDP relaxation of the equipartition problem is:

where*Z*is a 2*s*x 2*s*matrix and*C*_{ij}=*c*_{e}when the edge*e*=(*i*,*j*). How does the matrix*Z*relate to the matrices*X*and*W*given earlier? How can we exploit the results of Question 3 in this SDP formulation? What have we relaxed to arrive at this formulation?

John E. Mitchell