Due: Thursday, April 15, 2021.
Penalty for late homeworks: 10% for each day or part of a day.
- 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
- 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 χ
where λmax(A) and λmin(A) denote the largest and smallest eigenvalues of A respectively.
Assume E≠∅. Prove
- 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.)
Assume X is symmetric. Assume the 2 × 2 submatrices
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.)
- The package cvx is a modeling framework for convex optimization problems that works
within matlab. Install cvx, available from http://cvxr.com/cvx/download/
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
For a version of the code for solving non-random instances, see lovasztheta.m
example file edges8.mat
- 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