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

From EtoneWiki
Jump to: navigation, search

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

We consider minimum makespan scheduling on parallel identical machines when jobs are subject to precedence constraints.

We still want to schedule jobs on identical machines, where job has processing time . But now a partial order is defined on jobs, so that if then job must be completely finished before job begins. The following is a variant of the List algorithm for this problem: we still assume that the input is a list of jobs with processing times .

whenever a machine becomes idle
    assign the next available job on the list to the machine;

Here a job is available if all jobs have already been completely processed.

  • Prove that the approximation ratio is 2.