Srivastav, Anand and Stangier, Peter
(1996).
Algorithmic Chernoff-Hoeffding Inequalities in Integer Programming.
Wiley.
["eprint_fieldopt_monograph_type_preprint" not defined].
|
PDF
zpr93-147.pdf Download (372kB) | Preview |
Abstract
Proofs of classical Chernoff-Hoeffding bounds have 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 procedures, but a polynomial-time implementation was not known. We resolve this problem with an O(mn^2log frac{mn}{epsilon})-time algorithm, whenever the probability that all events hold is at least epsilon > 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.
| Item Type: | Preprints, Working Papers or Reports (["eprint_fieldopt_monograph_type_preprint" not defined]) | ||||||||||||
| Creators: |
|
||||||||||||
| URN: | urn:nbn:de:hbz:38-546822 | ||||||||||||
| Journal or Publication Title: | Random structures & algorithms | ||||||||||||
| Number: | 1 | ||||||||||||
| Page Range: | pp. 27-58 | ||||||||||||
| Date: | 1996 | ||||||||||||
| Publisher: | Wiley | ||||||||||||
| Language: | English | ||||||||||||
| Faculty: | Faculty of Mathematics and Natural Sciences | ||||||||||||
| Divisions: | Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science | ||||||||||||
| Subjects: | Data processing Computer science | ||||||||||||
| Refereed: | No | ||||||||||||
| URI: | http://kups.ub.uni-koeln.de/id/eprint/54682 |
Downloads
Downloads per month over past year
Export
Actions (login required)
 |
View Item |