Premium
Algorithmic Chernoff‐Hoeffding inequalities in integer programming
Author(s) -
Srivastav Anand,
Stangier Peter
Publication year - 1996
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199601)8:1<27::aid-rsa2>3.0.co;2-t
Subject(s) - chernoff bound , bernoulli's principle , mathematics , discrete mathematics , time complexity , constructive , integer lattice , combinatorics , algorithm , computer science , physics , half integer , process (computing) , quantum mechanics , engineering , aerospace engineering , operating system
Proofs of classical Chernoff‐Hoeffding bounds has been used to obtain polynomial‐time implementations of Spencer's derandomization method of conditional probabilities on usual finite machine models: given m events whose complements are large deviations corresponding to weighted sums of n mutually independent Bernoulli trials. Raghavan's lattice approximation algorithm constructs for 0‐1 weights, and integer deviation terms in O (mn)‐time a point for which all events hold. For rational weighted sums of Bernoulli trials the lattice approximation algorithm or Spencer's hyperbolic cosine algorithm are deterministic precedures, but a polynomial‐time implementation was not known. We resolve this problem with an O (mn 2 log \documentclass{article}\pagestyle{empty}\begin{document}$ {{mn}\over{\epsilon}} $\end{document} )‐time algorithm, whenever the probability that all events hold is at least ϵ > 0. Since such algorithms simulate the proof of the underlying large deviation inequality in a constructive way, we call it the algorithmic version of the inequality. Applications to general packing integer programs and resource constrained scheduling result in tight and polynomial‐time approximations algorithms. © 1996 John Wiley & Sons, Inc.