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

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