随机算法 (Fall 2015)/Problem Set 2

From EtoneWiki
Jump to: navigation, search

Problem 1

For any , a cut in an undirected (multi)graph is called an -min-cut if where is a min-cut in .

  • Give a lower bound to the probability that a single iteration of Karger's Random Contraction algorithm returns an -min-cut in a graph of vertices.
  • Use the above bound to estimate the number of distinct -min cuts in .


Problem 2

Suppose that we flip a fair coin times to obtain random bits. Consider all pairs of these bits in some order. Let be the exclusive-or of the th pair of bits, and let be the number of that equal 1.

  1. Show that the are NOT mutually independent.
  2. Show that the satisfy the property .
  3. Compute .
  4. Using Chebyshev's inequality, prove a bound on .

Problem 3

Show that the maximum load when balls are hashed into bins using a hash function chosen from a 2-universal family of hash functions is at most with probability at least 0.99. Generalize this argument to -universal hash functions.

Hint: Perhaps the only information we can use about a 2-universal hash function is the number of collisions. What does it become for -universal hashing?

  • (Optional) Can this be improved if the only thing we assume about the hash function is the 2-universality? Why?

Problem 4

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 5

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.)