New version page

USC CSCI 599 - 0420

Documents in this Course
Week8_1

Week8_1

22 pages

Week2_b

Week2_b

10 pages

LECT6BW

LECT6BW

20 pages

LECT6BW

LECT6BW

20 pages

5

5

44 pages

12

12

15 pages

16

16

20 pages

Nima

Nima

8 pages

Week1

Week1

38 pages

Week11_c

Week11_c

30 pages

afsin

afsin

5 pages

October5b

October5b

43 pages

Week11_2

Week11_2

20 pages

final

final

2 pages

c-4

c-4

12 pages

Week9_b

Week9_b

20 pages

S7Kriegel

S7Kriegel

21 pages

Week4_2

Week4_2

16 pages

sandpres

sandpres

21 pages

Week6_1

Week6_1

20 pages

4

4

33 pages

Week10_c

Week10_c

13 pages

fft

fft

18 pages

LECT7BW

LECT7BW

19 pages

24

24

15 pages

14

14

35 pages

Week9_c

Week9_c

24 pages

Week11_67

Week11_67

22 pages

Week1

Week1

37 pages

LECT3BW

LECT3BW

28 pages

Week8_c2

Week8_c2

19 pages

Week5_1

Week5_1

19 pages

LECT5BW

LECT5BW

24 pages

Week10_b

Week10_b

16 pages

Week11_1

Week11_1

43 pages

Week7_2

Week7_2

15 pages

Week5_b

Week5_b

19 pages

Week11_a

Week11_a

29 pages

LECT14BW

LECT14BW

24 pages

T7kriegel

T7kriegel

21 pages

0413

0413

2 pages

3

3

23 pages

C2-TSE

C2-TSE

16 pages

10_19_99

10_19_99

12 pages

s1and2-v2

s1and2-v2

37 pages

Week10_3

Week10_3

23 pages

jalal

jalal

6 pages

1

1

25 pages

T3Querys

T3Querys

47 pages

CS17

CS17

15 pages

porkaew

porkaew

20 pages

LECT4BW

LECT4BW

21 pages

Week10_1

Week10_1

25 pages

wavelet

wavelet

17 pages

October5a

October5a

22 pages

p289-korn

p289-korn

12 pages

2

2

33 pages

rose

rose

36 pages

9_7_99

9_7_99

18 pages

Week10_2

Week10_2

28 pages

Week7_3

Week7_3

37 pages

Load more
Upgrade to remove ads

This preview shows page 1 out of 3 pages.

Save
View Full Document
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience

Upgrade to remove ads
Unformatted text preview:

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
Download 0420
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view 0420 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view 0420 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?