MATP6620 / DSES6760
Combinatorial Optimization and Integer Programming
Homework 5.

Due: Monday, April 6, 2009.

1. Let $G$ be a bipartite graph. Prove that the complement of $G$ is a perfect graph.

2. Given a complete graph $G=(V,E)$ with edge weights $w_e$ and $n=kp$ nodes, we wish to partition the vertices into $k$ sets each containing exactly $p$ vertices so as to minimize the sum of the edge weights of the edges with endpoints in the same set. Let $e$ denote the $n$-vector of ones and let $w_{ii}=0$ for $i=1,\ldots,n$. Show that the following semidefinite program gives a lower bound on the optimal value of this problem, where $X$ is an $n \times n$ matrix:
   
   $$\begin{array}{lrcll} \min & 0.5 \sum_{i=1}^n \sum_{j=1}^n w_... ...n{2}{l}{\mbox{symmetric and positive semidefinite}} \end{array}$$
   
   

3. An instance of the symmetric traveling salesman problem on the complete graph $K_n$ on $n$ vertices has edge weights $w_e$ for each edge $e$. Let $W$ be the $n \times n$ matrix of edge weights, so $W$ is symmetric and the diagonal terms of $W$ are all zero. Let $C$ be the $n \times n$ adjacency matrix of the standard cycle on $K_n$, so
   
   $$C_{ij} \, = \, \left\{ \begin{array}{ll} 1 & \mbox{if } \ver... ...\vert i-j\vert=n-1 \\ 0 & \mbox{otherwise} \end{array}\right.$$
   
   
   Let $X$ be an $n \times n$ permutation matrix, so it has exactly one ``1'' in each row and each column, with the rest of the entries being zero. Given a Hamiltonian tour on $K_n$, show that a permutation matrix $X$ can be selected so that the value of the tour is equal to the trace of the $n \times n$ matrix $W X C X^T$. Conversely, show that if $X$ is a permutation matrix then the trace of $W X C X^T$ gives the value of a tour. (This result is the basis for an SDP relaxation of the traveling salesman problem.)

4. Let
   
   $$X \, = \, \left[ \begin{array}{lll} x_{11} & x_{12} & x_{13}... ...22} & x_{23} \\ x_{31} & x_{32} & x_{33} \end{array} \right].$$
   
   
   Assume $X$ is symmetric. Assume the $2\times 2$ submatrices
   
   $$\left[ \begin{array}{ll} x_{11} & x_{12} \\ x_{21} & x_{22} ... ...ray}{ll} x_{22} & x_{23} \\ x_{32} & x_{33}\end{array} \right]$$
   
   
   are positive semidefinite. Show that $x_{13}$ can be chosen so that $X$ is positive semidefinite. (This result can be generalized to allow an approach to solving semidefinite programs that exploits sparsity. The approach involves looking at cliques in chordal graphs.)

5. Give a progress report on your project. Your report should be at least a couple of paragraphs long. It doesn't need to repeat anything from your initial report from March 2.

	John Mitchell
	Amos Eaton 325
	x6915.
	mitchj at rpi dot edu
	Office hours: Office hours: Mondays, 1-3pm, or by appointment.