高级算法 (Fall 2017)/Problem Set 3

From EtoneWiki
Jump to: navigation, search

Problem 1

Consider the following optimization problem.

Instance: positive integers .
Find two disjoint nonempty subsets with , such that the ratio is minimized.

Give a pseudo-polynomial time algorithm for the problem, and then give an FPTAS for the problem based on the pseudo-polynomial time algorithm.

Problem 2

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 3

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 4

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 .

Problem 5

Recall that the instance of set cover problem is a collection of subsets , where is a universe of size . The goal is to find the smallest such that . The frequency is defined to be .

  • Give the primal integer program for set cover, its LP-relaxation and the dual LP.
  • Describe the complementary slackness conditions for the problem.
  • Give a primal-dual algorithm for the problem. Present the algorithm in the language of primal-dual scheme (alternatively raising variables for the LPs). Analyze the approximation ratio in terms of the frequency .