Homework Sample Solutions

In case you hadn’t noticed, we’ve been trying to put up sample solutions for the HWs: complete solutions for HW2, and partial solutions for HW3 are now online (I still need to write the solutions for HW3 #1).

Homework 2 graded

Homework 2 is graded. (Sorry for the delay, it’s my fault — AG).  The average was (20/25). Some comments:

1. Most people got this, although in some cases with pretty long-winded proofs.  The brief point is that when considering non-integral edges, every vertex on the V side has degree 0 or at least 2; thus one can find either a cycle (as in class) or else the maximal path starts and ends with a degree-1 vertex in U.  Deepak cleverly pointed out that you can also just add |U|-|V| fictitious jobs called “unemployment”, link everyone to them with weight 0, and then reduce to the proof from class.

2. George & Leslie = Nemhauser & Trotter.  Most people got this too, except in part (b) very few people observed out that for $x$ non-half-integral, $x^+$ and $x^-$ are distinct from $x$.  Since this was really the only point to the question we should have deducted a point for failing to mention it.  But we did not have the heart to do so.

3. Most people got the first 4 parts, and also the “easy” direction of Farkas Lemma (that both alternatives cannot be true). Some people had trouble with the last part (proving that if there is no feasible x then there must be a y): in particular, I saw proofs that tried to do it from first principles, where the hope was that you’d just use the template from the above parts (and use the correctness of the Avis-Kaluzny procedure).

4. This one tripped almost everyone up: very few of you even mentioned that one might not be able to reach the actual optimal LP value using binary search, and that some kind of “rounding” step would be needed at the end when the size of the binary search intervals is small enough. (That would have sufficed, since we didn’t really expect you to do this rounding step.) The details are all in the sample solutions: even if you don’t read all the solutions, have a look at this one for sure!

5. (Note: for this problem we should have stated that clauses always contain distinct literals.  But this didn’t seem to trip anyone up.)  Most everyone got (a) and (b).  To some extent the point of this question was that for (c), the analysis is much easier than the proof that Horn-Sat is in P.  All you have to do is say, “Given a solution with LP-value m, round each value down.”  It’s very quick to check that the resulting integer solution still has value m.

Lecture 12: SDP Duality

A draft of the SDP Duality lecture notes has been posted.

Lecture 11: The Lovasz Theta Function

A draft of the lecture notes on SDPs and The Lovasz Theta Function have been posted.

No Lecture on Tuesday

In case you missed the announcement the other day, Tuesday October 25th’s lecture is canceled due to the FOCS conference. Normal service will resume on Thursday.

Lecture #12 (SDP duality): discussion

1. Examples

The example showing that the optimum value of an SDP might not be achieved is this: subject to

For this to be positive-semidefinite, we need . But then the optimum value of the SDP is (it is the infimum of the values can take), but it not achieved by any feasible solution.

Here is an example where the primal is feasible and finite, but the dual is infeasible.

The optimum is , achieved by for . But the dual seeks to maximize subject to

But this is infeasible, since psd matrices cannot have non-zero entries in the same row/column as a zero diagonal entry.

2. Proofs of Some Useful Facts

We used several facts about matrices in lecture today, without proof. Here are some of the proofs. Recall that . For symmetric (and hence for psd) matrices, .

Fact 1 For any two matrices , Tr(AB) = Tr(BA).

Proof: .

Lemma 1 For a symmetric matrix , is psd if and only if for all psd .

Proof:
One direction is easy: if is not psd, then there exists for which . But is psd, which shows that for some psd .

In the other direction, let be psd. We claim that , defined by , is also psd. (This matrix is called the Schur-Hadamard product of and .) Then

by the definition of psd-ness of . To see the claim: since , there exist random variables such that . Similarly, let for r.v.s . Moreover, we can take the ‘s to be independent of the ‘s. So if we define the random variables , then

and we are done. (Note we used independence of the ‘s and ‘s to make the product of expectations the expectation of the product.)

This clean random variable-based proof is from this blog post. One can also show the following claim. (I don’t know of a slick r.v. based proof—anyone see one?) BTW, the linear-algebraic proof also gives an alternate proof of the above Lemma 1.

Lemma 2 For (i.e., it is positive definite), for all psd , .

Proof: Let’s write as where is orthonormal, and is the diagonal matrix containing ‘s eigenvalues (which are all positive, because .

Let , and hence . Note that is psd: indeed, . So all of ‘s diagonal entries are non-negative. Moreover, since , not all of ‘s diagonal entries can be zero (else, by ‘s psd-ness, it would be zero). Finally,

Since and for all , and for some , this sum is strictly positive.

Lemma 3 For psd matrices , if and only if .

Proof: Clearly if then .

For the other direction, we use the ideas (and notation) from Lemma 1. Again take the Schur-Hadamard product defined by . Then is also psd, and hence for random variables . Then

If this quantity is zero, then the random variable must be zero with probability . Now

so is identically zero.

3. Eigenvalues Seen Differently, or Old Friends Again

We saw that finding the maximum eigenvalue of a symmetric matrix can be formulated as:

and its dual

The dual can be reinterpreted as follows: recall that means we can find reals and unit vectors such that . By the fact that ‘s are unit vectors, , and the trace of this matrix is then . But by our constraints, , so .

Rewriting in this language, is the maximum of

such that the ‘s are unit vectors, and . But for any such solution, just choose the vector among these that maximizes ; that is at least as good as the average, right? Hence,

which is the standard variational definition of the maximum eigenvalue of .

Lecture 10: Semidefinite Programs and the Max-Cut Problem

A draft of the lecture notes on semidefinite programs and the Max-Cut problem is posted.

Lecture 9: More on Ellipsoid: Grötschel-Lovász-Schrijver theorems

Lecture notes on the Grötschel-Lovász-Schrijver theorems are posted.

Homework #4 comments

There’ve been some corrections to homework 4, just in case you missed those.

Also, for the matroid problem (#2): if you’ve not seen matroids before, you might find it useful to think about the arguments in the special case of the graphical matroid first. In a graphical matroid, the elements are edges of some graph G, and the independent sets are all forests (acyclic subgraphs) of this graph.

Lecture #11 discussion

In the lecture, I forgot to mention why we chose to talk about the classes of perfect graphs we did. We showed that bipartite graphs and line graphs of bipartite graphs (and their complements) are all perfect.Let’s call a graph basic if it belongs to one of these four classes: bip, co-bip, line(bip), or co-line(bip).

Recall a graph was called a Berge graph if it did not contain (as an induced subgraph) any odd hole or odd antihole. Clearly, all perfect graphs are Berge graphs, else they could contain such a offending induced subgraph, which would contradict their perfectness. The other direction is the tricky one: showing that all Berge graphs are perfect. Which is what Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas eventually did in 2002.

So how did they proceed? Here’s a mile-high view of their approach. They showed that every Berge graph either is basic (i.e., belongs to those four classes bip, co-bip, line(bip), or co-line(bip)), or else it has some structural “faults” ( has a 2-join, or its complement has a 2-join, or has an M-join, or a skew partition). For us, it does not matter what exactly these structural faults are: what matters is (and this is what CRST showed) that minimal imperfect graphs cannot have any of these faults. So, if Berge graphs could be imperfect, a minimal counterexample would be basic, which is a contradiction. More on this can be found, e.g., off the links on Vasek Chvatal’s Perfect Graph Theorem Page.

Re Srivatsan’s question: given the strong perfect graph theorem, the perfect graph theorem follows as a corollary. Indeed, suppose was perfect but was not. Then must not be a Berge graph, and contains either an odd hole or odd antihole as an induced subgraph. But then contains an odd antihole or odd hole as an induced subgraph, so could not have been perfect.