# 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 ${\displaystyle K}$ in ${\displaystyle n}$ dimensions, and estimate the volume ${\displaystyle K}$. Then we make the following idealized assumptions: for any convex body ${\displaystyle K}$, we can

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

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

Now consider the following problem:

Suppose that we have ${\displaystyle m}$ convex bodies ${\displaystyle K_{1},K_{2},\ldots ,K_{m}}$, in ${\displaystyle n}$ dimensions, provided by ${\displaystyle m}$ membership oracles ${\displaystyle {\mathcal {O}}_{1},{\mathcal {O}}_{2},\ldots ,{\mathcal {O}}_{m}}$, where for any ${\displaystyle n}$-dimensional point ${\displaystyle x}$, and any ${\displaystyle 1\leq i\leq m}$, ${\displaystyle {\mathcal {O}}_{i}(x)}$ indicates whether ${\displaystyle x\in K_{i}}$.

With the above ideal assumptions and inputs:

1. Give an FPRAS for ${\displaystyle \mathrm {vol} \left(\bigcap _{i=1}^{m}K_{i}\right)}$.
2. Give an FPRAS for ${\displaystyle \mathrm {vol} \left(\bigcup _{i=1}^{m}K_{i}\right)}$.

(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 ${\displaystyle {\mathcal {O}}_{1},{\mathcal {O}}_{2},\ldots ,{\mathcal {O}}_{m}}$, the uniform samples from convex ${\displaystyle K}$, and ${\displaystyle \mathrm {vol} (K)}$ for convex ${\displaystyle K}$.)

## Problem 2 (10 points)

Assumption: for a convex body ${\displaystyle K}$, we have a FPRAS for ${\displaystyle \mathrm {vol} (K)}$.

Let ${\displaystyle K\subseteq \mathbb {R} ^{n}}$ be a convex body in ${\displaystyle n}$ dimensions. Let ${\displaystyle f:\mathbb {R} ^{n}\rightarrow \mathbb {R} }$ be a linear function.

Describe how to estimate the value of ${\displaystyle {\frac {\int _{K}f(x)dx}{\int _{K}dx}}}$. 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 ${\displaystyle f(x)}$ might be negative.)

## Problem 3 (20 points)

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:

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 ${\displaystyle \{0,1\}}$ with the probability of the fractional value itself; and repeatedly apply this process to the variables rounded to 0 until every subset ${\displaystyle S_{i}\in {\mathcal {S}}}$ is "hited" once.

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