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.)
- 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 .