随机算法 (Fall 2011)/Problem set 3

Problem 1

A boolean code is a mapping [math]\displaystyle{ C:\{0,1\}^k\rightarrow\{0,1\}^n }[/math]. Each [math]\displaystyle{ x\in\{0,1\}^k }[/math] is called a message and [math]\displaystyle{ y=C(x) }[/math] is called a codeword. The code rate [math]\displaystyle{ r }[/math] of a code [math]\displaystyle{ C }[/math] is [math]\displaystyle{ r=\frac{k}{n} }[/math]. A boolean code [math]\displaystyle{ C:\{0,1\}^k\rightarrow\{0,1\}^n }[/math] is a linear code if it is a linear transformation, i.e. there is a matrix [math]\displaystyle{ A\in\{0,1\}^{k\times n} }[/math] such that [math]\displaystyle{ C(x)=Ax }[/math] for any [math]\displaystyle{ x\in\{0,1\}^k }[/math], where the additions and multiplications are defined over the finite field of order two, [math]\displaystyle{ (\{0,1\},+_{\bmod 2},\times_{\bmod 2}) }[/math].

The distance between two codeword [math]\displaystyle{ y_1 }[/math] and [math]\displaystyle{ y_2 }[/math], denoted by [math]\displaystyle{ d(y_1,y_2) }[/math], is defined as the Hamming distance between them. Formally, [math]\displaystyle{ d(y_1,y_2)=\|y_1-y_2\|_1=\sum_{i=1}^k|y_1(i)-y_2(i)| }[/math]. The distance of a code [math]\displaystyle{ C }[/math] is the minimum distance between any two codewords. Formally, [math]\displaystyle{ d=\min_{x_1,x_2\in \{0,1\}^k}d(C(x_1),C(x_2)) }[/math].

• Prove that there exists a bolean code [math]\displaystyle{ C:\{0,1\}^k\rightarrow\{0,1\}^n }[/math] of code rate [math]\displaystyle{ r }[/math] and distance [math]\displaystyle{ \left(\frac{1}{2}-\Theta\left(\sqrt{r}\right)\right)n }[/math].
• Prove a similar result for linear boolean codes.

Problem 2

Given a binary string, define a run as a maximal sequence of contiguous 1s; for example, the string 11100110011111101011 contains 5 runs, of length 3, 2, 6, 1, and 2.

Let [math]\displaystyle{ S }[/math] be a binary string of length [math]\displaystyle{ n }[/math], generated uniformly at random. Let [math]\displaystyle{ X_k }[/math] be the number of runs in [math]\displaystyle{ S }[/math] of length [math]\displaystyle{ k }[/math] or more.

• Compute the exact value of [math]\displaystyle{ \mathbb{E}[X_k] }[/math] as a function of [math]\displaystyle{ n }[/math] and [math]\displaystyle{ k }[/math].
• Give the best concentration bound you can for [math]\displaystyle{ |X_k − \mathbb{E}[X_k]| }[/math].

Problem 3

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:

1. Give an integer programming for the problem and its linear programming relaxation.
2. Consider the following idea of randomized rounding: independently round each fractional value to [math]\displaystyle{ \{0,1\} }[/math]; and repeatedly apply this process to the variables rounded to 0 until every subset [math]\displaystyle{ S_i\in\mathcal{S} }[/math] is "hited" once.

Use this idea to develop an randomized approximation algorithm and prove that your algorithm returns an [math]\displaystyle{ O(\log m) }[/math]-approximate solution with probability at least [math]\displaystyle{ \frac{1}{2} }[/math].