I was happy that my post on lift-and-project seemed to arouse interest. Since then, I browsed through a few papers to see how teaching lift-and-project might continue from there. I now have a plan:
Lecture 1: Introduction to lift-and-project, see previous post
Lecture 2: (Bienstock and Ozbay 2004) Consider independent set. If the underlying input graph has tree width bounded by a constant, then the Sherali-Adams lifted linear program is exact after only a constant number of lifts, meaning that its integrality gap equals 1 and that every solution of the lifted linear program is a convex combination of integer solutions.
Remember that the lifted variables can be interpreted as defining a distribution of integer solutions over the local set of vertices under consideration.
Then rounding a solution is easy: first pick the values v1,v2,...,vc (zero or one) of c variables in a first bag (x1,x2,...,xc) so that the "probability" y(x1=v1,x2=v2,...,xc=vc) is positive. Then repeatedy extend the values of a bag to a neighboring bag: if the neighboring bag has some variables (x1,x2,...,xd) in common with the old bag and some new variables (x'(d+1),...,x'c), pick the values for the new variables in a consistent manner, that is, so that
y(x1=v1,x2=v2,..xc=vc,x'(d+1)=v'(d+1),...,x'c=v'c) is positive.
Lecture 3: (Chlamtac Krauthgamer and Raghavendra 2010) Consider general demand sparsest cut. If the underlying input graph has tree width bounded by a constant r, then the Sherali-Adams lifted linear program has integrality gap O(1) after only a constant number of lifts. (The O(1) depends on r).
Then rounding a solution is easy: first sample the values v1,v2,...,vc (zero or one) of c variables in a first bag (x1,x2,...,xc) according to the distribution defined by the lifted variables y(x1=v1,x2=v2,...,xc=vc). Then repeatedy extend the values of a bag to a neighboring bag: if the neighboring bag has some variables (x1,x2,...,xd) in common with the old bag and some new variables (x'(d+1),...,x'c), sample the values for the new variables in a consistent manner, that is, according to the conditional distribution of the lifted LP variables for (x1,x2,...,xd,x'(d+1),...,x'c) given the values already chosen for variables (x1,x2,...,xd).
I believe that this sequence is a relatively simple presentation of lift-and-project for algorithms: the part about independent set is exact and, if reduced to its core and looked at from the right perspective, it can be made straightforward (maybe that will be material for another post). The part about sparsest cut is a new algorithmic result, the algorithm is a natural extension and the analysis, seen from a distance, feels right although it is a little bit technical - it uses a Markov flow graph, and going through that proof in class might be painful, but it's the best compromise I have found between the need for simplicity and elegance, and the desire to bring the class right at the threshold of open problems.
A nice result in this context is that of Magen and Moharrami in Approx 2009.
ReplyDeleteRobust algorithms for Maximum Independent Set on Minor-free graphs based on the Sherali-Adams Hierarchy.
It builds on the above mentioned paper of Bienstock and Ozbay to show that one can get a PTAS for max independent set and vertex cover for planar and minor-free graphs (and some extensions). It basically builds on the Baker framework for PTASes but shows the approximation with respect to an LP which is nice in that the class of graphs is of more general interest than bounded tree width graphs.
Chandra
I looked at the Magen-Moharrani paper and originally had a very positive outlook, but after spending a bit of time with it, I am not so impressed. With the right background knowledge and the right perspective and interpretation, it's relatively straightforward. I did not gain much insight from it. It seems - dare I write the dreaded word? - somewhat incremental... Of course, this is 2011, not 2009, so I admit that I have the advantage of looking back in time.
ReplyDeleteIn addition, I had been excited about their "PTAS" for independent set on near-planar graphs (planar graphs with o(n) extraneous edges), but they don't actually build an independent set on such graphs. They do prove that the LP has near-optimal value, but they do not know how to use that to round the LP solution and build a near-optimal independent set. I had looked forward to that, and was disappointed when it did not materialize.
I have not yet looked at the Chlamtac et al paper in detail, but I believe that it has much more depth.