A Primal-Dual Approach to Online Optimization Problems Online Optimization Problems вЂў input arrives вЂњpiece by pieceвЂќ (вЂњpieceвЂќ is called request) вЂў upon arrival of a request - has to be served immediately вЂў past decisions cannot be revoked how to evaluate the performance of an online algorithm? вЂ“ if, for each request sequence, cost(online) в‰¤ r x cost(optimal offline) вЂ“ then online algorithm is r-competitive Road Map Introducing the framework: вЂў Ski rental вЂў Online set cover вЂў Virtual circuit routing The general framework: вЂў {0,1} covering/packing linear programs вЂў General covering/packing linear programs Recent results: вЂў The ad-auctions problem вЂў Weighted caching The Ski Rental Problem вЂў Buying costs $B. вЂў Renting costs $1 per day. Problem: вЂў Number of ski days is not known in advance. Goal: Minimize the total cost. Ski Rental вЂ“ Integer Program пѓ¬1 - B uy пѓ¬1 - R ent on day i zi пЂЅ пѓ xпЂЅпѓ 0 - D on't rent on day i 0 D on't B uy пѓ® пѓ® k m in B x пЂ« пѓҐz i i пЂЅ1 Subject to: For each day i: x пЂ« z i п‚і 1 x , z i пѓЋ {0,1} Ski Rental вЂ“ Relaxation P: Primal Covering D: Dual Packing k m in B x пЂ« пѓҐz k i i пЂЅ1 For each day i: x пЂ« z i п‚і 1 x , zi п‚і 0 m ax пѓҐ y i i пЂЅ1 For each day i: y i п‚Ј 1 k пѓҐ yi п‚Ј B i пЂЅ1 Online setting: вЂў Primal: New constraints arrive one by one. вЂў Requirement: Upon arrival, constraints should be satisfied. вЂў Monotonicity: Variables can only be increased. Ski Rental вЂ“ Algorithm P: Primal Covering D: Dual Packing k m in B x пЂ« пѓҐz k m ax пѓҐ y i i i пЂЅ1 For each day i: x пЂ« z i п‚і 1 i пЂЅ1 For each day i: y i п‚Ј 1 x , zi п‚і 0 k пѓҐ i пЂЅ1 Initially xпѓџ 0 Each new day (new constraint): if x<1: п‚§ zi пѓџ 1-x п‚§ x пѓџ x(1+ 1/B) + 1/(c*B) п‚§ yi пѓџ 1 - вЂ�cвЂ™ later. yi п‚Ј B Analysis of Online Algorithm Proof of competitive factor: 1. Primal solution is feasible. 2. In each iteration, О”P в‰¤ (1+ 1/c)О”D. 3. Dual is feasible. Conclusion: Algorithm is (1+ 1/c)-competitive Initially xпѓџ 0 Each new day (new constraint): if x<1: п‚§ zi пѓџ 1-x п‚§ x пѓџ x(1+ 1/B) + 1/(c*B) п‚§ yi пѓџ 1 - вЂ�cвЂ™ later. Analysis of Online Algorithm 1. Primal solution is feasible. If x в‰Ґ1 the solution is feasible. Otherwise set: zi пѓџ 1-x. 2. In each iteration, О”P в‰¤ (1+ 1/c)О”D: Algorithm: If xв‰Ґ1, О”P =О”D=0 When new constraint Otherwise: arrives, if x<1: ziпѓџ1-x вЂў Change in dual: 1 xпѓџ x(1+ 1/B) + 1/c*B вЂў Change in primal: y пѓџ1 BО”x + zi = x+ 1/c+ 1-x = 1+1/c i Analysis of Online Algorithm 3. Dual is feasible: k Need to prove: пѓҐ y i п‚Ј B i пЂЅ1 We prove that after B days xв‰Ґ1 x is a sum of geometric sequence a1 = 1/(cB), q = 1+1/B B 1 пѓ¶ пѓ¦ 1 пЂ« пѓ§ пѓ· пЂ1 1 пѓЁ Bпѓё xпЂЅ пѓ— пЂЅ 1 пѓ¶ cB пѓ¦ 1 пЂ« пѓ§ пѓ· пЂ1 Bпѓё пѓЁ B 1 пѓ¶ пѓ¦ 1 пЂ« пѓ§ пѓ· пЂ1 Bпѓё пѓЁ c Algorithm: When new constraint arrives, if x<1: ziпѓџ1-x xпѓџ x(1+ 1/B) + 1/c*B yiпѓџ1 B 1 пѓ¶ пѓ¦ c п‚Ј пѓ§1 пЂ« пѓ· пЂ 1 п‚» e пЂ 1 Bпѓё пѓЁ 1 e 1пЂ« п‚» c e пЂ1 Randomized Algorithm 0 1 X: X1 X2 X3 X4 вЂў Choose d uniformly in [0,1] вЂў Buy on the day corresponding to the вЂњbinвЂќ d falls in вЂў Rent up to that day Analysis: вЂў Probability of buying on the i-th day is xi вЂў Probability of renting on the i-th day is at most zi Key Idea for Primal-Dual Primal: Min пѓҐi ci xi Dual: Max пѓҐt bt yt Step t, new constraint: a1x1 + a2x2 + вЂ¦ + ajxj в‰Ґ bt New variable yt + bt yt in dual objective xi пѓџ (1+ ai/ci) xi yt пѓџ yt + 1 (mult. update) (additive update) пЃ„ primal cost = = пЃ„ Dual Cost The Online Set-Cover Problem вЂў Elements: e1, e2, вЂ¦, en вЂў Set system: s1, s2, вЂ¦ sm вЂў Costs: c(s1), c(s2), вЂ¦ c(sm) Online Setting: вЂў Elements arrive one by one. вЂў Upon arrival elements need to be covered. вЂў Sets that are chosen cannot be вЂњunchosenвЂќ. Goal: Minimize the cost of the chosen sets. Set Cover вЂ“ Linear Program P: Primal Covering D: Dual Packing m ax пѓҐ y ( e ) m in пѓҐ c ( s ) x ( s ) eпѓЋ E sпѓЋ S пЂўe пѓЋ E пѓҐ s eпѓЋ s x(s) п‚і 1 пЂўs пѓЋ S пѓҐ y (e) п‚Ј c ( s ) eпѓЋ s Online setting: вЂў Primal: constraints arrive one by one. вЂў Requirement: each constraint is satisfied. вЂў Monotonicity: variables can only be increased. Set Cover вЂ“ Algorithm P: Primal Covering D: Dual Packing m ax пѓҐ y ( e ) m in пѓҐ c ( s ) x ( s ) eпѓЋ E sпѓЋ S пЂўe пѓЋ E пѓҐ x(s) п‚і 1 пЂўs пѓЋ S пѓҐ y (e) п‚Ј c ( s ) eпѓЋ s s eпѓЋ s Initially x(s)пѓџ 0 When new element arrives, while пѓҐ x ( s ) пЂј 1 : вЂў y(e) пѓџ y(e)+1 s eпѓЋ s вЂў .пЂў s e пѓЋ s x ( s ) п‚¬ x ( s ) пЂЁ 1 пЂ« 1 / c ( s ) пЂ© пЂ« 1 / пЃ› m пѓ— c ( s ) пЃќ Analysis of Online Algorithm Proof of competitive factor: 1. Primal solution is feasible. 2. In each iteration, О”P в‰¤ 2О”D. 3. Dual is (almost) feasible. Conclusion: We will see later. Initially x(S)пѓџ 0 When new element e arrives, while пѓҐ s eпѓЋ s x(s) пЂј 1 : вЂў y(e) пѓџ y(e)+1 вЂў . пЂў s e пѓЋ s x ( s ) п‚¬ x ( s ) пЂЁ1 пЂ« 1 / c ( s ) пЂ© пЂ« 1 / пЃ› m пѓ— c ( s ) пЃќ Analysis of Online Algorithm 1. Primal solution is feasible. We increase the primal variables until the constraint is feasible. Initially x(S)пѓџ 0 When new element e arrives, while пѓҐ s eпѓЋ s x(s) пЂј 1 : вЂў y(e) пѓџ y(e)+1 вЂў . пЂў s e пѓЋ s x ( s ) п‚¬ x ( s ) пЂЁ1 пЂ« 1 / c ( s ) пЂ© пЂ« 1 / пЃ› m пѓ— c ( s ) пЃќ Analysis of Online Algorithm 2. In each iteration, О”P в‰¤ 2О”D. In each iteration: вЂў О”D = 1 пѓ© x(s) пѓ№ 1 пЃ„ P = пѓҐ c(s) пѓ— пЃ„ x ( s ) пЂЅ пѓҐ c(s) пѓ— пѓЄ пЂ« пѓє c ( s ) m пѓ— c ( s ) s|eпѓЋs s|eпѓЋs пѓ« пѓ» пЂЅ пѓҐ s|eпѓЋ s x (s) пЂ« пѓҐ 1/m п‚Ј 2 s|eпѓЋ s Initially x(S)пѓџ 0 When new element e arrives, while пѓҐ s eпѓЋ s x(s) пЂј 1 : вЂў y(e) пѓџ y(e)+1 вЂў . пЂў s e пѓЋ s x ( s ) п‚¬ x ( s ) пЂЁ1 пЂ« 1 / c ( s ) пЂ© пЂ« 1 / пЃ› m пѓ— c ( s ) пЃќ Analysis of Online Algorithm 3. Dual is (almost) feasible: вЂў We prove that: пЂў s пѓЋ S , пѓҐ y(e) п‚Ј c(s)O (log m ) eпѓЋ S вЂў If y(e) increases, then x(s) increases (for e in S). вЂў x(s) is a sum of a geometric series: a1 = 1/[mc(s)], q = (1+ 1/c(s)) Initially x(S)пѓџ 0 When new element e arrives, while пѓҐ s eпѓЋ s x(s) пЂј 1 : вЂў y(e) пѓџ y(e)+1 вЂў . пЂў s e пѓЋ s x ( s ) п‚¬ x ( s ) пЂЁ1 пЂ« 1 / c ( s ) пЂ© пЂ« 1 / пЃ› m пѓ— c ( s ) пЃќ Analysis of Online Algorithm пѓЁ After c(s)O(log m) rounds: x(s) пЂЅ 1 пЂЁ пЃ›1 пЂ« 1 / c ( s ) пЃќ c ( s ) O (log m ) пЂ1 пЃ›1 пЂ« 1 / c ( s ) пЃќ пЂ 1 m пѓ— c(s) пЃ›1 пЂ« 1 / c ( s ) пЃќ пЂЁ пЂЅ c ( s ) O (log m ) пЂ1 пЂ© п‚і1 m We never increase a variable x(s)>1! Initially x(S)пѓџ 0 When new element e arrives, while пѓҐ s eпѓЋ s x(s) пЂј 1 : вЂў y(e) пѓџ y(e)+1 вЂў . пЂў s e пѓЋ s x ( s ) п‚¬ x ( s ) пЂЁ1 пЂ« 1 / c ( s ) пЂ© пЂ« 1 / пЃ› m пѓ— c ( s ) пЃќ пЂ© Conclusion вЂў The dual is feasible with cost 1/O(log m) of the primal. пѓЁ The algorithm produces a fractional set cover that is O(log m)-competitive. вЂў Remark: No online algorithm can perform better in general. What about an integral solution? вЂў Round fractional solution. (With O(log n) amplification.) вЂў Can be done deterministically online [AAABN03]. вЂў Competitive ratio is O(log m log n). Online Virtual Circuit Routing Network graph G=(V, E) capacity function u: Eпѓ Z+ Requests: ri = (si, ti) вЂў Problem: Connect si to ti by a path, or reject the request. вЂў Reserve one unit of bandwidth along the path. вЂў No re-routing is allowed. вЂў Load: ratio between reserved edge bandwidth and edge capacity. вЂў Goal: Maximize the total throughput. Routing вЂ“ Linear Program y ( ri , p ) P ( ri ) = Amount of bandwidth allocated for ri on path p - Available paths to serve request ri m ax пѓҐ ri пѓҐ y ( ri , p ) p пѓЋ P ( ri ) s.t: For each ri: пѓҐ y ( ri , p ) п‚Ј 1 p пѓЋ P ( ri ) For each edge e: пѓҐ ri пѓҐ p пѓЋ P ( ri ) eпѓЋ p y ( ri , p ) п‚Ј u ( e ) Routing вЂ“ Linear Program P: Primal Covering m in пѓҐ u ( e ) x ( e ) пЂ« eпѓЋ E D: Dual Packing пѓҐ z (r ) m ax пѓҐ i ri ri пЂў ri , p пѓЋ P ( ri ) : пЂў ri пѓҐ x(e) пЂ« z ( r ) п‚і 1 i eпѓЋ p пѓҐ пѓҐ y ( ri , p ) p пѓЋ P ( ri ) y ( ri , p ) п‚Ј 1 p пѓЋ P ( ri ) пЂўe : пѓҐ ri пѓҐ y ( ri , p ) п‚Ј u ( e ) p пѓЋ P ( ri ) e пѓЋ p Online setting: вЂў Dual: new columns arrive one by one. вЂў Requirement: each dual constraint is satisfied. вЂў Monotonicity: variables can only be increased. Routing вЂ“ Algorithm P: Primal Covering m in пѓҐ u ( e ) x ( e ) пЂ« eпѓЋ E D: Dual Packing пѓҐ z (r ) m ax пѓҐ i ri ri пЂў ri , p пѓЋ P ( ri ) : пЂў ri пѓҐ x(e) пЂ« z ( r ) п‚і 1 i eпѓЋ p пѓҐ пѓҐ y ( ri , p ) p пѓЋ P ( ri ) y ( ri , p ) п‚Ј 1 p пѓЋ P ( ri ) пЂўe : пѓҐ ri пѓҐ y ( ri , p ) п‚Ј u ( e ) p пѓЋ P ( ri ) e пѓЋ p Initially x(e)пѓџ 0 When new request arrives, if пЂ¤ p пѓЋ P ( ri ), пѓҐ x(e) пЂј 1 : eпѓЋ p п‚§ z(ri) пѓџ 1 пѓ¦ 1 пѓ¶ 1 п‚§ пЂў. e пѓЋ p : x ( e ) п‚¬ x ( e ) пѓ§ 1 пЂ« пѓ·пЂ« u (e ) пѓё n пѓ— u (e ) пѓЁ п‚§ y(ri,p) пѓџ 1 Analysis of Online Algorithm Proof of competitive factor: 1. Primal solution is feasible. 2. In each iteration, О”P в‰¤ 3О”D. 3. Dual is (almost) feasible. Conclusion: We will see later. Initially x(e)пѓџ 0 When new request arrives, if пЂ¤ p пѓЋ P ( ri ), пѓҐ x(e) пЂј 1 : eпѓЋ p п‚§ z(ri) пѓџ 1 пѓ¦ 1 пѓ¶ 1 п‚§ пЂў.e пѓЋ p : x ( e ) п‚¬ x ( e ) пѓ§ 1 пЂ« пѓ·пЂ« u (e ) пѓё n пѓ— u (e ) пѓЁ п‚§ y(ri,p) пѓџ 1 Analysis of Online Algorithm 1. Primal solution is feasible. If пЂў p пѓЋ P ( r ), пѓҐ x(e) п‚і 1 : the solution is feasible. i eпѓЋ p Otherwise: we update z(ri) пѓџ 1 Initially x(e)пѓџ 0 When new request arrives, if пЂ¤ p пѓЋ P ( ri ), пѓҐ x(e) пЂј 1 : eпѓЋ p п‚§ z(ri) пѓџ 1 пѓ¦ 1 пѓ¶ 1 п‚§ пЂў. e пѓЋ p : x ( e ) п‚¬ x ( e ) пѓ§ 1 пЂ« пѓ·пЂ« u (e ) пѓё n пѓ— u (e ) пѓЁ п‚§ y(ri,p) пѓџ 1 Analysis of Online Algorithm In each iteration: О”P в‰¤ 3О”D. If пЂў p пѓЋ P ( ri ) : пѓҐ x(e) п‚і 1 О”P = О”D=0 eпѓЋ p Otherwise: О”D=1 2. пЃ„P пЂЅ пѓҐ eпѓЋ p u ( e ) пЃ„ x ( e ) пЂ« z ( ri ) пѓ¦ x (e) пѓ¶ 1 пЂЅ пѓҐ u (e) пѓ§ пЂ« пѓ· пЂ«1п‚Ј 3 eпѓЋ p пѓЁ u (e) n пѓ— u (e) пѓё Initially x(e)пѓџ 0 When new request arrives, if пЂ¤ p пѓЋ P ( ri ), пѓҐ x(e) пЂј 1 : eпѓЋ p п‚§ z(ri) пѓџ 1 пѓ¦ 1 пѓ¶ 1 п‚§ пЂў. e пѓЋ p : x ( e ) п‚¬ x ( e ) пѓ§ 1 пЂ« пѓ·пЂ« u (e ) пѓё n пѓ— u (e ) пѓЁ п‚§ y(ri,p) пѓџ 1 Analysis of Online Algorithm 3. Dual is (almost) feasible. We prove: вЂў For each e, after routing u(e)O(log n) on e, x(e)в‰Ґ1 x(e) is a sum of a geometric sequence x(e)1 = 1/(nu(e)), q = 1+1/u(e) пѓЁ After u(e)O(log n) requests: u ( e ) O (log n ) пѓ¦ 1 пѓ¶ пЂ1 пѓ§1 пЂ« пѓ· u (e) пѓё 1 пѓЁ x (e) пЂЅ пѓ— пЂЅ n пѓ— u (e ) пѓ¦ 1 пѓ¶ пѓ§1 пЂ« пѓ· пЂ1 u (e) пѓё пѓЁ пѓ¦ 1 пѓ¶ пѓ§1 пЂ« пѓ· u ( e ) пѓЁ пѓё u ( e ) O (log n ) пЂ1 п‚і1 n New Results via P-D Approach: Routing Previous results (routing/packing): вЂў [AAP93] вЂ“ Route O(log n) fraction of the optimal without violating capacity constraints. Capacities must be at least logarithmic. вЂў [AAFPW94] вЂ“ Route all the requests with load of at most O(log n) times the optimal load. Observation [BN06] вЂ“ Both results can be described within the primal-dual approach. New Results via P-D Approach: Routing We saw a simple algorithm which is: вЂў 3-competitive and violates capacities by O(log n) factor. Can be improved [Buchbinder, Naor, FOCS06] to: вЂў 1-competitive and violates capacities by O(log n) factor. Non Trivial. Main ideas: вЂў Combination of ideas drawn from casting of previous routing algorithms within the primal-dual approach. вЂў Decomposition of the graph. вЂў Maintaining several primal solutions which are used to bound the dual solution, and for the routing decisions. New Results via P-D Approach: Routing Applications [Buchbinder, N, FOCS 06]: вЂў Can be used as вЂњblack boxвЂќ for many objective functions and in many routing models: вЂ“ Previous Settings [AAP93,APPFW94]. вЂ“ Maximizing throughput. вЂ“ Minimizing load. вЂ“ Achieving better global fairness results (Coordinate competitiveness). Road Map Introducing the framework: вЂў Ski rental вЂў Online set cover вЂў Virtual circuit routing The general framework: вЂў {0,1} covering/packing linear programs вЂў General covering/packing linear programs Recent results: вЂў The ad-auctions problem вЂў Weighted caching Online Primal-Dual Approach вЂў Can the offline problem be cast as a linear covering/packing program? вЂў Can the online process be described as: вЂ“ New rows appearing in a covering LP? вЂ“ New columns appearing in a packing LP? Yes ?? вЂў Upon arrival of a new request: вЂ“ Update primal variables in a multiplicative way. вЂ“ Update dual variables in an additive way. Online Primal Dual Approach Next Prove: 1. Primal solution is feasible (or nearly feasible). 2. In each round, О”P в‰¤ c О”D. 3. Dual is feasible (or nearly feasible). Got a fractional solution, but need an integral solution ?? вЂў вЂў Randomized rounding techniques might work. Sometimes, even derandomization (e.g., method of conditional probabilities) can be applied online! Online Primal-Dual Approach Advantages: 1. Generic ideas and algorithms applicable to many online problems. 2. Linear Program helps detecting the difficulties of the online problem. 3. General recipe for the design and analysis of online algorithms. 4. No potential function appearing вЂњout of nowhereвЂќ. 5. Competitiveness with respect to a fractional optimal solution. General Covering/Packing Results What can you expect to get? вЂў For a {0,1} covering/packing matrix: вЂ“ Competitive ratio O(log D) [BN05] (D вЂ“ max number of non-zero entries in a constraint). Remarks: вЂў Fractional solutions. вЂў Number of constraints/variables can be exponential. вЂў There can be a tradeoff between the competitive ratio and the factor by which constraints are violated. General Covering/Packing Results вЂў For a general covering/packing matrix [BN05] : Covering: вЂ“ Competitive ratio O(log n) (n вЂ“ number of variables). Packing: вЂ“ Competitive ratio O(log n + log [a(max)/a(min)]) a(max), a(min) вЂ“ maximum/minimum non-zero entry Remarks: вЂў Results are tight. Special Cases The max number of non-zero entries in a constraint is a constant? вЂў You can get a constant ratio. The max number of non-zero entries in a constraint is 2? вЂў Calls for an e/(e-1)-ratio. Examples: вЂў Ski rental, Online matching, Ad-Auctions. Known Results via P-D Approach Covering Online Problems (Minimization): вЂў O(log k)-algorithm for weighted caching [BBN07] вЂў Ski rental, Dynamic TCP Acknowledgement вЂў Parking Permit Problem [Meyerson 05] вЂў вЂў Online Set Cover [AAABN03] Online Graph Covering Problems [AAABN04]: вЂ“ вЂ“ вЂ“ вЂ“ Non-metric facility location Generalized connectivity: pairs arrive online Group Steiner: groups arrive online Online multi-cut: (s,t)--pairs arrive online Known Results via P-D Approach Packing Online Problems (maximization): вЂў Online Routing/Load Balancing Problems [AAP93, AAPFW93, BN06]. вЂў вЂў вЂў General Packing/routing e.g. Multicast trees. Online Matching [KVV91] вЂ“ Nodes arrive one-by-one. Ad-Auctions Problem [MSVV05] вЂ“ In a bit вЂ¦ Road Map Introducing the framework: вЂў Ski rental вЂў Online set cover вЂў Virtual circuit routing The general framework: вЂў {0,1} covering/packing linear programs вЂў General covering/packing linear programs Recent results: вЂў The ad-auctions problem вЂў Weighted caching What are Ad-Auctions? You type in a search engine: Vacation Eilat You get: And вЂ¦ Advertisements Algorithmic Search results How do search engines sell ads? вЂў Each advertiser: вЂ“ Sets a daily budget вЂ“ Provides bids on interesting keywords вЂў Search Engine (on each keyword): вЂ“ Selects ads вЂ“ Advertiser pays bid if user clicks on ad. Goal (of Search engine): Maximize revenue Mathematical Model вЂў Buyer i: вЂ“ Has a daily budget B(i) вЂў Online Setting: вЂ“ Items (keywords) arrive one-by-one. вЂ“ Each buyer gives a bid on each of the items (can be zero) вЂў Algorithm: вЂ“ Assigns each item to some interested buyer. Assumption: Bids are small compared to the daily budget. Ad-Auctions вЂ“ Linear Program B(i) вЂ“ Budget of buyer i b(i,j) вЂ“ bid of buyer i on item j I - Set of buyers. J - Set of items. y (i , j ) = 1 пѓћ j-th ad-auction is sold to buyer i. m ax пѓҐ iпѓЋ I s.t: For each item j: jпѓЋ J пѓҐ y (i , j ) п‚Ј 1 iпѓЋ I For each buyer i: пѓҐ b (i, j ) y (i, j ) Each item is Buyers do not sold once. exceed their budget пѓҐ b (i , j ) y (i , j ) п‚Ј B (i ) jпѓЋ J Results [MSVV FOCS 05]: вЂў (1-1/e)-competitive online algorithm. вЂў Bound is tight. вЂў Analysis uses tradeoff revealing family of LPвЂ™s - not very intuitive. Our Results [Buchbinder, Jain, N, 2007]: вЂў A different approach based on the primal-dual method: very simple and intuitive вЂ¦ and extensions. вЂў Techniques are applicable to many other problems. The Paging/Caching Problem Set of n pages, cache of size k<n. Request sequence of pages 1, 6, 4, 1, 4, 7, 6, 1, 3, вЂ¦ If requested page is in cache, no penalty. Else, cache miss! And load page into cache, (possibly) evicting some page. Goal: Minimize the number of cache misses. Main Question: Which page to evacuate? Previous Results: Paging Paging (Deterministic) [Sleator Tarjan 85]: вЂў Any det. algorithm >= k-competitive. вЂў LRU is k-competitive (also other algorithms) вЂў LRU is k/(k-h+1)-competitive if optimal has cache of size h<k Paging (Randomized): вЂў Rand. Marking O(log k) [Fiat, Karp, Luby, McGeoch, Sleator, Young 91]. вЂў Lower bound Hk [Fiat et al. 91], tight results known. вЂў O(log(k/k-h+1))-competitive algorithm if optimal has cache of size h<k [Young 91] The Weighted Paging Problem One small change: вЂў Each page i has a different load cost w(i). вЂў Models scenarios in which the cost of bringing pages is not uniform: Main memory, disk, internet вЂ¦ web Goal вЂў Minimize the total cost of cache misses. Weighted Paging (Previous Work) Randomized Deterministic Paging Weighted Paging Lower bound k LRU k competitive k-competitive [Chrobak, Karloff, Payne, Vishwanathan 91] k/(k-h+1) if optвЂ™s cache size h k/(k-h+1) O(log k) Randomized Marking O(log k) for two weight classes O(log k/(k-h+1)) [Young 94] [Irani 02] No o(k) algorithm known even for 3 weight classes. The k-server Problem вЂў k servers lie in an n-point metric space. вЂў Requests arrive at metric points. вЂў To serve request: Need to move some server there. Goal: Minimize total movement cost вЂў Paging = k-server on a uniform metric. (every page is a point, page in cache iff server on the point) вЂў Weighted paging = k-server on a weighted star metric. The k-server Problem вЂў k servers lie in an n-point metric space. вЂў Requests arrive at metric points. вЂў To serve request: Need to move some server there. Goal: Minimize total movement cost (2k-1) Det. Work Function Alg [Koutsoupias, Papadimitriou 95] Randomized. No o(k) known (even for very simple spaces). Best lower bound пЃ—(log k) (widely believed conjecture) Our Results Weighted Paging (Randomized): (Bansal, Buchbinder, N., FOCS 2007) вЂў O(log k)-competitive algorithm for weighted paging. вЂў O(log (k/k-h+1))-competitive if optвЂ™s cache size h<k. Much simpler than previous approaches. Metrical Task System (Randomized): вЂў O(log N)-competitive algorithm on a weighted star metric. вЂў Closely related to k-server problem (details in paper вЂ¦) Further Research Generalized Caching вЂў Pages have both sizes and fetching costs. вЂў Motivation: Web-Caching Special models: вЂў Bit model: Fetching cost proportional to size (minimize traffic) вЂў Fault model: Fetching cost is uniform (minimize number of times a user has to wait for a page) Results (Bansal, Buchbinder, N., 2008): вЂў O(log k)-competitive algorithms for Bit and Fault models. вЂў O(log2k)-competitive algorithm for the general model. вЂў Requires new interesting ideas and interesting analysis in the rounding phase. Further Research вЂў More applications. вЂў Extending the general framework beyond packing/covering. вЂў The k-server problem? Thank you

1/--страниц