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

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

- Show that the are
**NOT**mutually independent. - Show that the satisfy the property .
- Compute .
- 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.)