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

- sample uniformly from in time polynomial of ;
- compute its volume precisely in time polynomial of .

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

Now consider the following problem:

Suppose that we have convex bodies , in dimensions, provided by membership oracles , where for any -dimensional point , and any , indicates whether .

With the above ideal assumptions and inputs:

- Give an FPRAS for .
- Give an FPRAS for .

(**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 , the uniform samples from convex , and for convex .)

## Problem 2 (10 points)

Assumption: for a convex body , we have a FPRAS for .

Let be a convex body in dimensions. Let be a linear function.

Describe how to estimate the value of . 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 might be negative.)

## Problem 3 (20 points)

The set cover problem is defined as follows:

- Let be a set of elements, and let be a family of subsets of . For each , let be a nonnegative weight of . The goal is to find a subset with the minimum total weight , that intersects with all .

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 with the probability of the fractional value itself; and repeatedly apply this process to the variables rounded to 0 until every subset is "hited" once.

Use this idea to develop an randomized approximation algorithm which returns an -approximate solution with probability at least .