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

Problem 1

For any [math]\displaystyle{ \alpha\ge 1 }[/math], a cut [math]\displaystyle{ C }[/math] in an undirected (multi)graph [math]\displaystyle{ G(V,E) }[/math]is called an [math]\displaystyle{ \alpha }[/math]-min-cut if [math]\displaystyle{ |C|\le\alpha|C^*| }[/math] where [math]\displaystyle{ C^* }[/math] is a min-cut in [math]\displaystyle{ G }[/math].

• Give a lower bound to the probability that a single iteration of Karger's Random Contraction algorithm returns an [math]\displaystyle{ \alpha }[/math]-min-cut in a graph [math]\displaystyle{ G(V,E) }[/math] of [math]\displaystyle{ n }[/math] vertices.

• Use the above bound to estimate the number of distinct [math]\displaystyle{ \alpha }[/math]-min cuts in [math]\displaystyle{ G }[/math].

Problem 2

Suppose that we flip a fair coin [math]\displaystyle{ n }[/math] times to obtain [math]\displaystyle{ n }[/math] random bits. Consider all [math]\displaystyle{ m={n\choose 2} }[/math] pairs of these bits in some order. Let [math]\displaystyle{ Y_i }[/math] be the exclusive-or of the [math]\displaystyle{ i }[/math]th pair of bits, and let [math]\displaystyle{ Y=\sum_{i=1}^m Y_i }[/math] be the number of [math]\displaystyle{ Y_i }[/math] that equal 1.

1. Show that the [math]\displaystyle{ Y_i }[/math] are NOT mutually independent.
2. Show that the [math]\displaystyle{ Y_i }[/math] satisfy the property [math]\displaystyle{ \mathbf{E}[Y_iY_j]=\mathbf{E}[Y_i]\mathbf{E}[Y_j] }[/math].
3. Compute [math]\displaystyle{ \mathbf{Var}[Y] }[/math].
4. Using Chebyshev's inequality, prove a bound on [math]\displaystyle{ \Pr[|Y-\mathbf{E}[Y]|\ge n] }[/math].

Problem 3

Show that the maximum load when [math]\displaystyle{ n }[/math] balls are hashed into [math]\displaystyle{ n }[/math] bins using a hash function chosen from a 2-universal family of hash functions is at most [math]\displaystyle{ O(\sqrt{n}) }[/math] with probability at least 0.99. Generalize this argument to [math]\displaystyle{ k }[/math]-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 [math]\displaystyle{ k }[/math]-universal hashing?

• (Optional) Can this [math]\displaystyle{ O(\sqrt{n}) }[/math] 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 [math]\displaystyle{ G=(V,E) }[/math], with each directed edge [math]\displaystyle{ (u,v)\in E }[/math] having a nonnegative weight [math]\displaystyle{ w_{uv}\ge 0 }[/math]. The goal is to partition [math]\displaystyle{ V }[/math] into two sets [math]\displaystyle{ S\, }[/math] and [math]\displaystyle{ \bar{S}=V\setminus S }[/math] so as to maximize the value of [math]\displaystyle{ \sum_{(u,v)\in E\atop u\in S,v\not\in S}w_{uv} }[/math], that is, the total weight of the edges going from [math]\displaystyle{ S\, }[/math] to [math]\displaystyle{ \bar{S} }[/math].

• Give a randomized [math]\displaystyle{ \frac{1}{4} }[/math]-approximation algorithm based on random sampling.
• Prove that the following is an integer programming for the problem:

[math]\displaystyle{ \begin{align} \text{maximize} && \sum_{(i,j)\in E}w_{ij}z_{ij}\\ \text{subject to} && z_{ij} &\le x_i, & \forall (i,j)&\in E,\\ && z_{ij} &\le 1-x_j, & \forall (i,j)&\in E,\\ && x_i &\in\{0,1\}, & \forall i&\in V,\\ && 0 \le z_{ij}&\le 1, & \forall (i,j)&\in E. \end{align} }[/math]

• Consider a randomized rounding algorithm that solves an LP relaxation of the above integer programming and puts vertex [math]\displaystyle{ i }[/math] in [math]\displaystyle{ S }[/math] with probability [math]\displaystyle{ f(x_i^*) }[/math]. We may assume that [math]\displaystyle{ f(x) }[/math] is a linear function in the form [math]\displaystyle{ f(x)=ax+b }[/math] with some constant [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math] to be fixed. Try to find good [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math] so that the randomized rounding algorithm has a good approximation ratio.

Problem 5

The set cover problem is defined as follows:

• Let [math]\displaystyle{ U=\{u_1,u_2,\ldots,u_n\} }[/math] be a set of [math]\displaystyle{ n }[/math] elements, and let [math]\displaystyle{ \mathcal{S}=\{S_1,S_2,\ldots,S_m\} }[/math] be a family of subsets of [math]\displaystyle{ U }[/math]. For each [math]\displaystyle{ u_i\in U }[/math], let [math]\displaystyle{ w_i }[/math] be a nonnegative weight of [math]\displaystyle{ u_i }[/math]. The goal is to find a subset [math]\displaystyle{ V\subseteq U }[/math] with the minimum total weight [math]\displaystyle{ \sum_{i\in V}w_i }[/math], that intersects with all [math]\displaystyle{ S_i\in\mathcal{S} }[/math].

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:

[math]\displaystyle{ \begin{align} \text{minimize} && \sum_{(i,j)\in E}w_{i}x_{i}\\ \text{subject to} && \sum_{i:u_i\in S_j}x_i &\ge 1, &1\le j\le m,\\ && x_i &\in\{0,1\}, & 1\le i\le n. \end{align} }[/math]

• Give a randomized rounding algorithm which returns an [math]\displaystyle{ O(\log m) }[/math]-approximate solution with probability at least [math]\displaystyle{ \frac{1}{2} }[/math]. (Hint: you may repeat the randomized rounding process if there remains some uncovered subsets after one time of applying the randomized rounding.)