Randomized Algorithms (Spring 2010)/Problem Set 5

Problem 1 (20 points)

In class, we learn that with the presence of a membership oracle, we can sample near uniformly from any convex body [math]\displaystyle{ K }[/math] in [math]\displaystyle{ n }[/math] dimensions, and estimate the volume [math]\displaystyle{ K }[/math]. Then we make the following idealized assumptions: for any convex body [math]\displaystyle{ K }[/math], we can

• sample uniformly from [math]\displaystyle{ K }[/math] in time polynomial of [math]\displaystyle{ n }[/math];
• compute its volume [math]\displaystyle{ \mathrm{vol}(K) }[/math] precisely in time polynomial of [math]\displaystyle{ n }[/math].

(Note that in both assumptions, the errors are ignored.)

Now consider the following problem:

Suppose that we have [math]\displaystyle{ m }[/math] convex bodies [math]\displaystyle{ K_1,K_2,\ldots,K_m }[/math], in [math]\displaystyle{ n }[/math] dimensions, provided by [math]\displaystyle{ m }[/math] membership oracles [math]\displaystyle{ \mathcal{O}_1,\mathcal{O}_2,\ldots,\mathcal{O}_m }[/math], where for any [math]\displaystyle{ n }[/math]-dimensional point [math]\displaystyle{ x }[/math], and any [math]\displaystyle{ 1\le i\le m }[/math], [math]\displaystyle{ \mathcal{O}_i(x) }[/math] indicates whether [math]\displaystyle{ x\in K_i }[/math].

With the above ideal assumptions and inputs:

1. Give an FPRAS for [math]\displaystyle{ \mathrm{vol}\left(\bigcap_{i=1}^mK_i\right) }[/math].
2. Give an FPRAS for [math]\displaystyle{ \mathrm{vol}\left(\bigcup_{i=1}^mK_i\right) }[/math].

(Remark: for both questions, you should explicitly describe the algorithm, and give mathematically sound analysis. The only unspecified calls of subroutines should be the membership oracles [math]\displaystyle{ \mathcal{O}_1,\mathcal{O}_2,\ldots,\mathcal{O}_m }[/math], the uniform samples from convex [math]\displaystyle{ K }[/math], and [math]\displaystyle{ \mathrm{vol}(K) }[/math] for convex [math]\displaystyle{ K }[/math].)

Problem 3 (20 points)

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] with the probability of the fractional value itself; 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 which returns an [math]\displaystyle{ O(\log m) }[/math]-approximate solution with probability at least [math]\displaystyle{ \frac{1}{2} }[/math].