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

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

- Give a poly-time greedy algorithm for finding the weighted max -cut. Prove that the approximation ratio is .
- 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 nextavailablejob 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.