Autumn 2010 Algorithms II

1 Approximation Algorithms

1. Vertex cover

2. General set cover

3. The Art Gallery problem

4. Weighted set cover

5. Maximum cut and maximum weighted cut

6. Knapsack and bin packing.

7. Rounding Linear Programs for designing approximation algorithms

8. Linear Programming duality and analysis of greedy approximation algorithms

(a) Weak duality

(b) Optimality and complementary slackness

(c) Dual fitting analysis technique for the greedy set cover heuristic

2 Amortization

1. 2-4 Trees (a) Insertion in 2-4 trees

(b) Time required for a batch of n insertions

(c) Time required for a batch of insertion and deletion operations

2. Binary counter

3. Examples of other algorithms including some from geometric algorithms like triangulation, shortest paths and convex hulls.

3 Geometric Algorithms

1. Convex hull algorithms– incremental.

2. Triangulation of a point set – incremental.

3. Outlines of shortest paths and visibility algorithms as applications and related to triangulations and Graham’s scan ideas.

4. Kirkpatrick’s planar point location scheme.

4 Dynamic programming algorithms for opti-

mization problems

1. Upsequences in an unsorted sequence

2. Computing the maximum independent set in a tree

3. Optimal bitonic tour

4. Optimal triangulation examples for polygons.

5 Randomization and derandomization

1. The method of expectations of the first moment for hypergraph bicoloring 2. A simple LAS VEGAS method for proper bicoloring of hypergraphs

3. Derandomizing using the method of conditional probabilities for bicoloring hypergraphs

4. A simple MONTE CARLO method for computing the minimum cut 5. The method of random sampling for a set system or hypergraph

(a) Binomial random sampling of the set of vertices

(b) ϵ-nets and ϵ-approximations

(c) Deterministic construction of ϵ-nets

6. Random sampling for geometric/searching applications

7. Examples illustrating the probabilistic method

8. Discrepancy upper bounds and derandomization using the method of conditional expectations

(a) An upper bound for combinatorial discrepancy using tail bounds (b) A relaxed upper bound and a LAS VEGAS algorithm for generating

a bicoloring with bounded discrepancy

(c) Derandomizing for generating a bicoloring with the relaxed bounded discrepancy using the method of conditional expectations

6 Graph algorithms

1. The maxflow-mincut theorem

2. Greedy flow algorithms

3. Edmond-Karp O(|E|^{2}|V |) algorithm for finding the maximum flow in a network

7 Semi-numerical algorithms

1. The O(n log n) FFT algorithm for polynomial multiplication.