Categories and Subject Descriptors ×òíòú×Y óüóòDó×ùDó××óùDò èó×ó×ó.pdf

arXiv:cs/0703100v1 [] 21 Mar 2007 Approximation Algorithms for Multiprocessor Scheduling under Uncertainty Guolong Lin ? Akamai Technologies 8 Cambridge Center, Cambridge, MA 02142 glin@ Rajmohan Rajaraman College puter and Information Science Northeastern University, Boston MA 02115 ABSTRACT n m Cj i p ij j i C O(logn) O(logmlognlog(n+m)/log log(n+m)) C O(logmlog 2n) C O(logmlog 2nlog(n+m)/log log(n+m)) C Categories and Subject Descriptors General Terms Keywords ? Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for pro?t mercial advantage and that copies bear this notice and the full citation on the ?rst page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior speci?c permission and/or a fee. SPAA’07,June 9–11, 2007, San Diego, California, USA. Copyright 2007 ACM978-1-59593-667-7/07/0006 ...$. 1. INTRODUCTION m n j i p ij j i Our results ? O(logn) ? O(logmlogn log(n+m) log log(n+m) ) ? O(logmlog 2n) O(logmlog 2n log(n+m) log log(n+m) ) Related work 5/4 p ij m n i j i j i j i j 2. SCHEDULES, ESS PROBABILITIES, AND MASS Schedules J n M m C j t j t j i p ij j i j i p ij>0 Σ T∈Z +∪{∞} {f S,t:M→J∪{⊥}|S?J,1≤ t < T+ 1} Σ t S i f S,t(i) f S,t(i) S i f S,t tj ?i, p ij<1 Σ g f S,t(·) =f S,t(·) S?J t 16=t 2 f S,t S Σ g {f S:M→S∪{⊥} |S?J} T j i p ij>0 t t t 2 n S f S f S,t S t, S, S ′f S,t(·) =f S,t(·) t f t t S t S t ess probabilities and mass S?M j j 1? Qi∈S(1?p ij) x 1,· · ·, x k∈[0,1]1?(1? x 1)· · ·(1?x k)≤x 1+· · ·+x k x 1+· · ·+x k≤ 1 1?(1?x 1)· · ·(1?x k)≥e ?1(x 1+· · ·+x k) (1? x 1)· · ·(1?x k)≥1?(x 1+· · ·+x k) k= 1 k?1 x 1+ · · ·+x k?1>1 k (1?x 1)· · ·(1?x k?1)(1?x k) ≥[1?(x 1+· · ·+x k?1)](1?x k) ≥1?(x 1+· · ·+x k). 0≤x≤11?x≤ e ?x≤1? xe 1?x≤e ?x(1?x 1)· · ·(1?x k)≤ e ?x· · ·e ?x 1?(1?x 1)· · ·(1?x k) ≥1?e ?x· · ·e ?x = 1?e ?(x+···+x) ≥ x 1+· · ·+x k e , e ?x