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

Problem 1

For any ${\displaystyle \alpha \geq 1}$, a cut ${\displaystyle C}$ in an undirected (multi)graph ${\displaystyle G(V,E)}$is called an ${\displaystyle \alpha }$-min-cut if ${\displaystyle |C|\leq \alpha |C^{*}|}$ where ${\displaystyle C^{*}}$ is a min-cut in ${\displaystyle G}$.

• Give a lower bound to the probability that a single iteration of Karger's Random Contraction algorithm returns an ${\displaystyle \alpha }$-min-cut in a graph ${\displaystyle G(V,E)}$ of ${\displaystyle n}$ vertices.
• Use the above bound to estimate the number of distinct ${\displaystyle \alpha }$-min cuts in ${\displaystyle G}$.

Problem 2

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

1. Show that the ${\displaystyle Y_{i}}$ are NOT mutually independent.
2. Show that the ${\displaystyle Y_{i}}$ satisfy the property ${\displaystyle \mathbf {E} [Y_{i}Y_{j}]=\mathbf {E} [Y_{i}]\mathbf {E} [Y_{j}]}$.
3. Compute ${\displaystyle \mathbf {Var} [Y]}$.
4. Using Chebyshev's inequality, prove a bound on ${\displaystyle \Pr[|Y-\mathbf {E} [Y]|\geq n]}$.

Problem 3

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

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

• Give a randomized ${\displaystyle {\frac {1}{4}}}$-approximation algorithm based on random sampling.
• Prove that the following is an integer programming for the problem:
{\displaystyle {\begin{aligned}{\text{maximize}}&&\sum _{(i,j)\in E}w_{ij}z_{ij}\\{\text{subject to}}&&z_{ij}&\leq x_{i},&\forall (i,j)&\in E,\\&&z_{ij}&\leq 1-x_{j},&\forall (i,j)&\in E,\\&&x_{i}&\in \{0,1\},&\forall i&\in V,\\&&0\leq z_{ij}&\leq 1,&\forall (i,j)&\in E.\end{aligned}}}
• Consider a randomized rounding algorithm that solves an LP relaxation of the above integer programming and puts vertex ${\displaystyle i}$ in ${\displaystyle S}$ with probability ${\displaystyle f(x_{i}^{*})}$. We may assume that ${\displaystyle f(x)}$ is a linear function in the form ${\displaystyle f(x)=ax+b}$ with some constant ${\displaystyle a}$ and ${\displaystyle b}$ to be fixed. Try to find good ${\displaystyle a}$ and ${\displaystyle b}$ so that the randomized rounding algorithm has a good approximation ratio.

Problem 5

The set cover problem is defined as follows:

• Let ${\displaystyle U=\{u_{1},u_{2},\ldots ,u_{n}\}}$ be a set of ${\displaystyle n}$ elements, and let ${\displaystyle {\mathcal {S}}=\{S_{1},S_{2},\ldots ,S_{m}\}}$ be a family of subsets of ${\displaystyle U}$. For each ${\displaystyle u_{i}\in U}$, let ${\displaystyle w_{i}}$ be a nonnegative weight of ${\displaystyle u_{i}}$. The goal is to find a subset ${\displaystyle V\subseteq U}$ with the minimum total weight ${\displaystyle \sum _{i\in V}w_{i}}$, that intersects with all ${\displaystyle S_{i}\in {\mathcal {S}}}$.

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:
{\displaystyle {\begin{aligned}{\text{minimize}}&&\sum _{(i,j)\in E}w_{i}x_{i}\\{\text{subject to}}&&\sum _{i:u_{i}\in S_{j}}x_{i}&\geq 1,&1\leq j\leq m,\\&&x_{i}&\in \{0,1\},&1\leq i\leq n.\end{aligned}}}
• Give a randomized rounding algorithm which returns an ${\displaystyle O(\log m)}$-approximate solution with probability at least ${\displaystyle {\frac {1}{2}}}$. (Hint: you may repeat the randomized rounding process if there remains some uncovered subsets after one time of applying the randomized rounding.)