# 随机算法 \ 高级算法 (Fall 2016)/Problem Set 1

每道题目的解答都要有完整的解题过程。中英文不限。

## Problem 1

For any , a cut in an undirected (multi)graph is called an -min-cut if where is a min-cut in .

- Give a lower bound to the probability that Karger's Random Contraction algorithm returns an -min-cut in a graph of vertices.
- Use the above bound to estimate the number of distinct -min cuts in .

## Problem 2

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 3

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 4

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.

## Problem 5

For a **hypergraph** with vertex set , every **hyperedge** is a subset of vertices, not necessarily of size 2. A hypergraph is **-uniform** if every hyperedge is of size .

A hypergraph is said to have **property B** (named after Bernstein) if is 2-coloable; that is, if there is a **proper 2-coloring** which assigns each vertex one of the two colors Red or Blue, such that none of the hyperedge is *monochromatic*.

- Let be a -uniform hypergraph in which every hyperedge shares vertices with at most other hyperedges.
- Prove that if , then has property B.
- Describe how to use Moser's recursive Fix algorithm to find a proper 2-coloring of . Give the pseudocode. Prove the condition in in terms of and under which the algorithm can find a 2-coloring of with high probability.
- Describe how to use Moser-Tardos random solver to find a proper 2-coloring of . Give the pseudocode. Prove the condition in in terms of and under which the algorithm can find a 2-coloring of within bounded expected time. Give an upper bound on the expected running time.

- Let be a hypergraph (not necessarily uniform) with at least vertices satisfying that
- .

- Prove that has property B.
- Describe how to use Moser-Tardos random solver to find a proper 2-coloring of . Give an upper bound on the expected running time.