随机算法 (Spring 2014)/Problem Set 3

From EtoneWiki
Jump to: navigation, search

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:
.
  1. 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.)
  2. 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.)