Randomized Algorithms (Spring 2010)/Problem Set 5

From EtoneWiki
Jump to: navigation, search

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:

  1. Give an FPRAS for .
  2. 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.)


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