高级算法 (Fall 2018)/Problem Set 4

From EtoneWiki
Jump to: navigation, search

Note: in this problem set, problem 1 and 2 are mandatory. For problem 3 to 5, you are only required to solve arbitrary two of them. (But you are also welcome to hand in solutions for them all!)

Problem 1

Let be an undirected graph with positive edge weights . Given a partition of into disjoint subsets , we define

as the cost of the -cut . Our goal is to find a -cut with maximum cost.

  1. Give a poly-time greedy algorithm for finding the weighted max -cut. Prove that the approximation ratio is .
  2. Consider the following local search algorithm for the weighted max cut (max 2-cut).
Fill in the blank parenthesis. Give an analysis of the running time of the algorithm. And prove that the approximation ratio is 0.5.
start with an arbitrary bipartition of  into disjoint ;
while (true) do
   if  and  such that (______________)
      then  leaves  and joins ;
      continue;
   end if
   break;
end

Problem 2

Given subsets of a universe of size , we want to find a of fixed size with the maximum coverage .

  • Give a poly-time greedy algorithm for the problem. Prove that the approximation ratio is .


Problem 3

In the maximum directed cut (MAX-DICUT) problem, we are given as input a directed graph . The goal is to partition into disjoint and so that the number of edges in is maximized. The following is the integer program for MAX-DICUT:

Let denote the optimal solution to the LP-relaxation of the above integer program.

  • Apply the randomized rounding such that for every , independently with probability . Analyze the approximation ratio (between the expected size of the random cut and OPT).
  • Apply another randomized rounding such that for every , independently with probability . Analyze the approximation ratio for this algorithm.

Problem 4

Recall the MAX-SAT problem and its integer program:

Recall that are the respective sets of variables appearing positively and negatively in clause .

Let denote the optimal solution to the LP-relaxation of the above integer program. In our class we learnt that if is round to 1 independently with probability , we have approximation ratio .

We consider a generalized rounding scheme such that every is round to 1 independently with probability for some function to be specified.

  • Suppose is an arbitrary function satisfying that for any . Show that with this rounding scheme, the approximation ratio (between the expected number of satisfied clauses and OPT) is at least .
  • Derandomize this algorithm through conditional expectation and give a deterministic polynomial time algorithm with approximation ratio .
  • Is it possible that for some more clever we can do better than this? Try to justify your argument.

Problem 5

The following is the weighted version of set cover problem:

Given subsets , where is a universe of size , and each subset is assigned a positive weight , the goal is to find a such that and the total weight is minimized.

  • Give an integer program for the problem and its LP 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 in previous iterations until is fully covered. Show that this can return a set cover with approximation ratio with probability at least .