View source for 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>K</math> in <math>n</math> dimensions, and estimate the volume <math>K</math>. Then we make the following idealized assumptions: for any convex body <math>K</math>, we can
* sample uniformly from <math>K</math> in time polynomial of <math>n</math>;
* compute its volume <math>\mathrm{vol}(K)</math> precisely in time polynomial of <math>n</math>.

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

Now consider the following problem:

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

With the above ideal assumptions and inputs:
# Give an FPRAS for <math>\mathrm{vol}\left(\bigcap_{i=1}^mK_i\right)</math>.
# Give an FPRAS for <math>\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>\mathcal{O}_1,\mathcal{O}_2,\ldots,\mathcal{O}_m</math>, the uniform samples from convex <math>K</math>, and <math>\mathrm{vol}(K)</math> for convex <math>K</math>.)

==Problem 2 (10 points) ==
Assumption: for a convex body <math>K</math>, we have a FPRAS for <math>\mathrm{vol}(K)</math>.

Let <math>K\subseteq \mathbb{R}^n</math> be a convex body in <math>n</math> dimensions. Let <math>f:\mathbb{R}^n\rightarrow\mathbb{R}</math> be a linear function.

Describe how to estimate the value of <math>\frac{\int_K f(x)dx}{\int_Kdx}</math>. Is your method an FPRAS? If not, give a suitable condition under which it is an FPRAS.

('''Hint''': Consider the relation between integrations and volumes.)


('''Notice''': The range of <math>f(x)</math> might be negative.)

==Problem 3 (20 points) ==
The set cover problem is defined as follows:
*Let <math>U=\{u_1,u_2,\ldots,u_n\}</math> be a set of <math>n</math> elements, and let <math>\mathcal{S}=\{S_1,S_2,\ldots,S_m\}</math> be a family of subsets of <math>U</math>. For each <math>u_i\in U</math>, let <math>w_i</math> be a nonnegative weight of <math>u_i</math>. The goal is to find a subset <math>V\subseteq U</math> with the minimum total weight <math>\sum_{i\in V}w_i</math>, that intersects with all <math>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:
# Give an integer programming for the problem and its linear programming relaxation.
# Consider the following idea of randomized rounding: independently round each fractional value to <math>\{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>S_i\in\mathcal{S}</math> is "hited" once.

Use this idea to develop an randomized approximation algorithm which returns an <math>O(\log m)</math>-approximate solution with probability at least <math>\frac{1}{2}</math>.