随机算法 (Spring 2014)/Problem Set 3
Contents
Problem 1
(Due to J. Naor.)
The Chernoff bound is an exponentially decreasing bound on tail distributions. Let be independent random variables and for all . Define . We can use the following two kinds of tail inequalities for .
- Chernoff Bounds:
- .
- th-Moment Bound:
- .
- Show that for each , there exists a choice of such that the th-moment bound is stronger than the Chernoff bound. (Hint: You may use the probabilistic method.)
- Why would we still prefer the Chernoff bound to the seemingly stronger th-moment bound?
Problem 2
Given a binary string, define a run as a maximal sequence of contiguous 1s; for example, the following string
contains 5 runs, of length 3, 2, 6, 1, and 2.
Let be a binary string of length , generated uniformly at random. Let be the number of runs in of length or more.
- Compute the exact value of as a function of and .
- Give the best concentration bound you can for .
Problem 3
- The maximum directed cut problem (MAX-DICUT).
We are given as input a directed graph , with each directed edge having a nonnegative weight . The goal is to partition into two sets and so as to maximize the value of , that is, the total weight of the edges going from to .
- Give a randomized -approximation algorithm based on random sampling.
- Prove that the following is an integer programming for the problem:
- Consider a randomized rounding algorithm that solves an LP relaxation of the above integer programming and puts vertex in with probability . We may assume that is a linear function in the form with some constant and to be fixed. Try to find good and so that the randomized rounding algorithm has a good approximation ratio.
Problem 4
The set cover problem is defined as follows:
- Let be a set of elements, and let be a family of subsets of . For each , let be a nonnegative weight of . The goal is to find a subset with the minimum total weight , that intersects with all .
This problem is NP-hard.
(Remark: There are two equivalent definitions of the set cover problem. We take the hitting set version.)
Questions:
- Prove that the following is an integer programming for the problem:
- Give a randomized rounding algorithm which returns an -approximate solution with probability at least . (Hint: you may repeat the randomized rounding process if there remains some uncovered subsets after one time of applying the randomized rounding.)