MATP6620 / ISYE6760
Integer and Combinatorial Optimization

Homework 5.

Due: Thursday, April 15, 2021.
Penalty for late homeworks: 10% for each day or part of a day.

  1. Given a complete graph G = (V,E) with edge weights we 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 wii = 0 for i = 1,,n. Show that the following semidefinite program gives a lower bound on the optimal value of this problem, where X is an n × n matrix:
    min        0.5 ∑n   ∑n    w  X
                 i=1   j=1  ij  ij
subject to                   Xii  =   1   i = 1, ...,n
                             Xe   =   pe
                              X       symmetric   and positive semide finite

  2. The coloring number χ of an undirected graph G = (V,E) is the smallest number of colors needed to color the vertices V so that no two adjacent vertices share a color. Let n = |V | and let A denote the n × n adjacency matrix. The Hoffman bound on χ is
            λ    (A)
χ ≥ 1 - --max---

    where λmax(A) and λmin(A) denote the largest and smallest eigenvalues of A respectively. Assume E. Prove

    λmax(A ) > 0 > λmin(A).

  3. Recall the Hoffman bound from Question 2. Show the bound is tight if G is a complete bipartite graph with E. (In a complete bipartite graph, V can be partitioned into two sets V 1 and V 2, every vertex in V 1 is adjacent to every vertex in V 2, no vertex in V 1 is adjacent to any other vertex in V 1, and no vertex in V 2 is adjacent to any other vertex in V 2.)
  4. Let
          ⌊               ⌋
        x11  x12  x13
X  =  ⌈ x21  x22  x23 ⌉ .
        x31  x32  x33

    Assume X is symmetric. Assume the 2 × 2 submatrices

    [          ]          [          ]
  x11  x12     and      x22  x23
  x21  x22              x32  x33

    are positive semidefinite. Show that x13 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. The package cvx is a modeling framework for convex optimization problems that works within matlab. Install cvx, available from

    Use it to solve the Lovász theta relaxation of some randomly generated node packing problems using the routine lovaszthetarand.m

    You need to select 2 parameters in matlab: the matrix size msize, and density which controls the number of edges in the graph. The expected number of edges is

                        (        )
          density     msize
E (E ) = -----------      2       for 0 ≤ density ≤  1.
        1 + density

    For a version of the code for solving non-random instances, see lovasztheta.m and an example file edges8.mat

  6. 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 Homework 3.
    John Mitchell
    Amos Eaton 325
    mitchj at rpi dot edu
    Office hours: Monday and Thursday 1pm–2pm.