随机算法 (Fall 2011)/Problem set 3: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>Etone
Created page with "==Problem 3 == The set cover problem is defined as follows: *Let <math>U=\{u_1,u_2,\ldots,u_n\}</math> be a set of <math>n</math> elements, and let <math>\mathcal{S}=\{S_1,S_2,\l…"
 
imported>Etone
Line 9: Line 9:
Questions:
Questions:
# Give an integer programming for the problem and its linear programming relaxation.
# 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 <math>\{0,1\}</math> with the probability of the fractional value itself; and repeatedly apply this process to the variables rounded to 0 until every subset <math>S_i\in\mathcal{S}</math> is "hited" once.
# Consider the following idea of randomized rounding: independently round each fractional value to <math>\{0,1\}</math>; and repeatedly apply this process to the variables rounded to 0 until every subset <math>S_i\in\mathcal{S}</math> is "hited" once.


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

Revision as of 07:53, 6 November 2011

Problem 3

The set cover problem is defined as follows:

  • Let [math]\displaystyle{ U=\{u_1,u_2,\ldots,u_n\} }[/math] be a set of [math]\displaystyle{ n }[/math] elements, and let [math]\displaystyle{ \mathcal{S}=\{S_1,S_2,\ldots,S_m\} }[/math] be a family of subsets of [math]\displaystyle{ U }[/math]. For each [math]\displaystyle{ u_i\in U }[/math], let [math]\displaystyle{ w_i }[/math] be a nonnegative weight of [math]\displaystyle{ u_i }[/math]. The goal is to find a subset [math]\displaystyle{ V\subseteq U }[/math] with the minimum total weight [math]\displaystyle{ \sum_{i\in V}w_i }[/math], that intersects with all [math]\displaystyle{ S_i\in\mathcal{S} }[/math].

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 [math]\displaystyle{ \{0,1\} }[/math]; and repeatedly apply this process to the variables rounded to 0 until every subset [math]\displaystyle{ S_i\in\mathcal{S} }[/math] is "hited" once.

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