PDF《Stochastic燢napsack》

2 13 By?Claim? ?i=1 n ei ・ Pr[Ti=1] Thus??x?∈ LP Scaled?LP max???i=1 n wi ・ xi max???i=1 n wi ・ xi s.t. ?i=1 n ei ・ xi ≤

2 s.t. ?i=1 n ei ・ xi ≤

1 0?≤ x≤ 1. 0?≤ x≤ 1. ? LP(1)?more?convenient?to?work?with ? Note?LP*(1)?≥ LP*(2)/2?≥ OPT/2 x?∈ LP(2)?? x/2?∈ LP(1) ? LP*(1)?has?x1?=?x2?=?? =?xk =?1,??xk+1=θ where: e1 +?e2?+?+?ek +?θ・ ek+1 =?1 ? So?LP*(1)?≤ w1 +?w2 +?+?wk+1

14 e1 ek ek+1

1 ? w1/e1 ≥ w2 /e2 ? ≥ wk /ek?≥ ? e2 Algorithm G?:=?{1,2,?,k},??OPT/2?≤ LP*(1)?≤ w(G) +?wk+1 ≤ w(G) +?wmax Algorithm:?Run?one?of?the?following?w.p.???each: 1. Place?best?single job Expected?reward?ALG1 ≥ wmax 2. Place?jobs?of?G as: Expected?reward?ALG2 Lemma:?ALG2 ≥ w(G)/2?C wmax/2 ? ALG?=???ALG1 +???ALG2?≥ w(G)/4?+?wmax/4?≥ OPT/8 Theorem:??8\approximation?for?stochastic?knapsack. Also?adaptivity gap?≤

8 15

1 2 k k k\1

1 or ? ? Analysis?of?ALG2 ALG2 : G?=?{1,2,?,k} Lemma:?ALG2 ≥ w(G)/2?C wmax/2 ? S'i :=?min?{?Si ,?1?},?so?E[S'i]?=?ei ? Job?v?yields?reward???v?fits?in?knapsack???S'v +??i?v S'i ≤ 1? ? E?[??i?v S'i ] =???・ e(G\v) ? Pr [?v?doesn't?fit?]?≤ E?[?S'v+?i?v S'i ]?≤ e(G)/2+ev/2?≤ ??+?ev/2 ? ALG2 =??v∈G rv・Pr[v?fits]?≥ ?v∈G wv・(1/2?C ev/2)? ≥ w(G)/2 C wmax/2

16 e(G) =??v∈G ev ≤

1 Markov's?ineq.

1 2 k k k\1

1 or ? ? Better?Bounds Stochastic?Knapsack ? 4\approx?and?adaptivity gap???[Dean?Goemans Vondrak '08] ? Stronger?LP?relaxation?for?AD\OPT ? Better?analysis?of?NA?algorithm ? 3\approx?adaptive?algorithm???[Dean?Goemans Vondrak '08] ? (2+?)\approx adaptive?algorithm???[Bhalgat Goel Khanna?'11]

17 18 Outline 1. Stochastic?knapsack?(SK)?basics 2. Non\adaptive?algorithm?for?SK 3. Correlated?stochastic?knapsack?(CSK) Non\adaptive?algorithm 4. Adaptive?algorithm?for?CSK 5. Extensions Correlated?Stochastic?Knapsack ? Job?rewards?Ri also?random,?correlated?to?size?Si Joint?distribution??Pr?[Ri=a ,?Si=b] ? Different?jobs?independent ? Max?expected?reward?s.t.?budget?B ? Assume?all?sizes?are?integral ? Assume?Si ∈ {0,?1,?? B}?=?[B] Wlog.?by?zeroing?reward?for?larger?sizes? ? Distribution?i?=??(pit?,?rit)?for?t?∈ [B] pit =?Pr[Si=t]?,??rit =?E[Ri |?Si=t]

19 S=1 R?=?1 Pr=1/2 S=5 R?=?3 Pr=1/2 [Gupta?Krishnaswamy Molinaro Ravi?'11] Distribution?Information?Used ? In?uncorrelated?case,?we?only?used: Capped?mean?size?ei =?E[min(Si ,?B)] Effective?reward?wi =?E[Ri ・ 1Si≤B] ? SOL1 =?i,?i,? has?reward?

1 ? SOL2 =?j,?j,? has?reward? B/2 Need?to?use?more?info?from?distribution?in?CSK

20 S=B/(B\1) R=0 Pr=1\1/B S=B R=B Pr=1/B S=2 R=1 Pr=1 job?i job?j ei =?ej =?2 wi =?wj =?1 ? Previous?LP/algorithm?insufficient? LP?Relaxation?for?CSK?(1) Use?capped?mean?and?reward?at?all?sizes?t?∈ [B]?: eit :=?E[min(Si ,?t)] wit :=?E[Ri ・ 1Si≤B\t] max? ?i=1 n ?t=0 B wit ・ xit s.t. ?i=1 n eit ・?s=0 t xis ≤ 2t,????? t∈[B] ?t=0 B xit ≤ 1,??? ? i∈[n] x?≥ 0. Theorem:?LP*?≥ OPT.

21 Time?indexed?LP LP?Relaxation?for?CSK?(2) max? ?i=1 n ?t=0 B wit ・ xit s.t. ?i=1 n eit ・ ?s=0 t xis ≤ 2t,????? t∈[B] ?t=0 B xit ≤ 1,??? ? i∈[n] x?≥ 0.? Tit :=?indicator?OPT?starts?job?i @?time?t Consider?LP?solution??xit =?Pr[Tit=1] Claim?1:??t=0 B wit ・ xit =?OPT E[reward?from?i |?Tit=1]?=?E[Ri ・ 1Si≤B\t]?=?wit Claim?2:???i=1 n min{Si ,?t}?・ ?s=0 t Tis ≤ 2t In?any?decision?path,?at?most?one job?running?@?time?t

22 B t

0 t

0 2t job?i Non\Adaptive?Algorithm 1) Solve?time\indexed?LP?relaxation poly(n,B)?time 2) For?each?i,?set?Di = 3) Place?jobs?i1,?i2,?? in by?non\decreasing?Dis Theorem: 8\approx.?for?correlated?stochastic?knapsack Lemma: Pr[i starts?by?t?|?Di=t]?≥ ???for?all?i∈[n]?,?t