Algorithmic Chernoff-Hoeffding Inequalities in Integer
Animd Srivastav · 1996
Proo!;; of cla~sic:;l Chernoff-Hoeffding bounds have been us~d to obtain polynomi al-time implementations of Spencer's derandomization method of conditional proba bilities Oll .llsual tinite machine models: given m events whose eomplements are large dc~iations~orrespoilding tq wcighted sums of n Inutually independent Bernoulli trials) Raghavan's 'faltice approxiitlation algorithrn eonstructs for 0 - 1 weights and integer deviation termsih O(inn)-til'ru~a point forwhich allevents hold. For rational weighted sums of Bernoulli trials the lattice approximation algorithm or Spencer's hyperbolic eosine algorithm are deterministie proeedures, hut a polynomial-time implementa bon was not kliown ..We '~esolve this problem with an O(rhri 2 Tog r: n )-tinIi:~ algorithm, whenever the probability that all events hold is at least f> O. Since such algorithms simulate the pruofof the underlying large deviation incquality·in- a construetive way; we caU it th~ algorithmic version of the inequality, Applications togeneral packing int.eger progran~s, aD-d l'es,ouree const.rained schedulillg result in -:(;ightand polynomial time app~o~imatioIlS algorithms.