O'Reilly logo

Concentration of Measure for the Analysis of Randomized Algorithms by Alessandro Panconesi, Devdatt P. Dubhashi

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

6

The Simple Method of Bounded Differences in Action

In this chapter we shall see the “method of bounded differences”, namely, Corollary 5.2 in action by applying it to various examples of increasing sophistication.

6.1 Chernoff–Hoeffding Revisited

Let X1, . . . , Xn be independent variables taking values in [0, 1], and consider f(x1, . . . , xn) := ∑i xi. Then, of course, f has the Lipschitz property with each di = 1 in (5.9), and by Corollary 5.2, we get for X := X1 + · · · + Xn the classical Chernoff–Hoeffding bound

image

6.2 Stochastic Optimisation: Bin Packing

The bin-packing problem is a well-studied combinatorial optimisation problem: we are ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required