CS599: Approximation Algorithms April 20th, 2010Maximizing Submodular Functions over MatroidsLecturer: David Kempe Scribe: Mengchen Wang and Hsing-Hau Chen1 The Continuous Greedy AlgorithmIn the previous lecture, we introduced the overall approach to the problem of maximizing submodularfunctions over matroids. Having defined a suitable fractional version of the problem, we now give theapproximate continuous greedy algorithm for solving the fractional version.Algorithm 1 Continuous Greedy Algorithm (~y(t) is a p oint in P at time t)1: Start with ~y(0) =~0.2: Continuously, for 1 unit of time total, move in the direction of maximum gradient∂~y∂t= ˆv(~y(t)), whereˆv(~y(t)) ∈ arg max~v∈P~v · ∇F (~y(t))It is fairly easy to show that without loss of generality, at each time t, ˆv(~y(t)) is a combination of basisvectors ~yS(as opposed to other independent sets). Otherwise, we could simple replace the αS> 0 for somenon-basis set S with αS′for some basis S′⊇ S, achieving no smaller gradient.Remark 1 To turn this into an actual algorithm, there are some technical issues that we will return to inthe next lecture.1. We need to discretize time so that we can run the algorithm in a finite number of steps. How does thisaffect the approximation?2. How can we evaluate F (~y)?3. How do we find the arg max?We first show the the algorithm returns a feasible solution, and then analyze its approximation quality.Proposition 2 Algorithm 1 gives a feasible solution. That is, ~y(1) ∈ P.Proof. The basic idea underlying the proof is that we construct a convex combination of points in thepolytope, which is again in the polytope.For each time t, the direction is a convex combination of bases: ˆv(~y(t)) =PSαt,S·~yS, wherePSαt,S= 1,and αt,S≥ 0. Therefore, ~y(1) =R10ˆv(~y(t)) dt =PS~ySR10αt,Sdt.LetR10αt,Sdt = βS≥ 0. We havePSβS=R10PSαt,Sdt =R101 dt = 1. Therefore, ~y(1) is a convexcombination of ~yS, and ~y(1) ∈ P.Proposition 3 Algorithm 1 is a factor (1 −1e) app roximation algorithm.Proof. Let ~x be an optimum vector. Thus, we have OPT = F (~x). Define ~v = min(~x − ~y(t),~0), coordinate-wise. (The idea in this definition and the subsequent proof is similar to when we were looking at f (S ∪OPT)−f(S) in the analysis of the Nemhauser-Wolsey algorithm.) By concavity (which we proved last class),F (~x)−F (~y(t)) ≤ 1 ·~v ·∇F (~y(t)), where 1 denotes one unit of time. Because the matroid is downward closed,so is P, i.e., if ~z ∈ P and~z′≤ ~z coordinate-wise, then~z′∈ P. In our case, ~v ≤ ~x coordinate-wise, so ~v ∈ P,and was a candidate for ˆv(~y(t)).1Write g(t) := F (~y(t)) for the algorithm’s function value at time t. Then,dgdt≥ OPT − g(t) by the choiceof the algorithm. We have g(0) = 0, and we want g(1). Sincedgdt≥ OPT − g(t), g(t) is lower-bounded bythe solution todφdt= OPT − φ(t).Let ψ(t) = OPT − φ(t). Then φ(t) = OPT − ψ(t). With the substitution, we obtaindφdt= −dψdt,so the differential equation becomes −dψdt= ψ(t). Integrating asRT0−dψψ=RT0dt gives us a solution of− logψ(t)ψ(0)= t, or ψ(t) = OPT · e−t. Substituting back, we find that φ(t) = OPT · (1 − e−t), and with t = 1,this gives us φ(1) = OPT · (1 −1e).2 Pipage RoundingHaving found a fractional solution ~y = ~y(1), we next want to round it to an integral solution (a basis).We will introduce a technique called Pipage Rounding for this. The idea is as follows. While there arefractional entries yi, yj∈ (0, 1), replace the pair by yi+ δ, yj− δ or yi− δ, yj+ δ such that at least one ofyi, yjbecomes integral, and the quality of the solution does not decrease (too much). In trying to apply thisgeneral technique in our case, we have two issues to deal with:1. We have to make sure that the objective does not decrease at all in our case. (In other applications ofPipage Rounding, it might decrease.)2. While ideally, we would like to make at least one variable integral, this may not always work in ourcase: there may be matroid polytope constraints that prevent us from making variables integral. Inthat case, we need a systematic way to find a pair (i, j) of variables for which making them integralworks. We will achieve this with a more careful progress measure than just the number of integralentries.But first, we want to show that there is always (at least) one direction in which the solution does not getany worse.Proposition 4 While there are fractional entries yi, yj∈ (0, 1) in the fractional solution, at least one ofreplacing the pair by yi+ δ, yj− δ or yi− δ, yj+ δ does not decrease the objective.Proof. For fixed i, j, define Fyij(t) := F (~y + t ·~dij), wheredij,k=1, if k = i−1, if k = j0, otherwiseThat is, we increase yiat the same rate at which we decrease yj, and vice versa.To see whether Fyij(t) decreases or not, we calculate the derivative and the second derivative.dFyijdt=∂F∂yi−∂F∂yj,d2Fyijdt2=∂2F∂y2i−∂2F∂yi∂yj−∂2F∂yj∂yi+∂2F∂y2j.Since∂2F∂y2i=∂2F∂y2j= 0, and∂2F∂yi∂yj≤ 0 (which we saw in the last lecture), we haved2Fyijdt2= −2 ·∂2F∂yi∂yj≥ 0Since the second derivative is non-negative, it follows that Fyijis convex. The convexity of Fyij(t) impliesthat it cannot have a local maximum. That is, in at least one direction of positive/negative t, F does notdecrease.2Since the objective does not decrease at all, we would be doing great if we could always make one of yi, yjintegral, but there may be other faces of P preventing it. We identify such faces with the sets of variablesthey correspond to, and call these sets of variables tight. We define the notion of tightness in terms of therank of a set.Definition 5 1. The rank of set A is rankM(A) = maxS∈I,S⊆A|S|.2. Writing y(A) :=Pi∈Ayi, we define a set A as tight for ~y if and only if y(A) = rankM(A).Notice that y(A) ≤ rankM(A) for every feasible vector ~y and set A, because each y ∈ P is a convexcombination of ~yS, S ∈ I, and ~yS(A) ≤ rankM(A), for all S ∈ I. The name “rank” is motivated by thelinear matroid: the rank of a set of vectors (a matrix) is the maximum number of linearly independentvectors in the
View Full Document
Unlocking...