Possible topics for presentation in the TDG

"Classical" approximation algorithms

Algortihms based on semidefinite programing. I would suggest the paer Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems by Goemns and Williamson

The Goemans-Williamson algorithm for constrained forest problems. A General Approximation Technique for Constrained Forest Problems

J. Kleinberg and E. Tardos. Approximation Algorithms for Classification Problems with Pairwise Relationships:Metric Partitioning and Markov Random Fields

The Jain-Vazirani facility location and k-median algorithm. Facility Location and k-Median Problems Using the Primal-Dual Schema and Lagrangian Relaxation
Kamal Jain: A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem.

The Held-Karp bound for the metric Traveling Salesman problem.

The best known approximation algorithm for metric TSP is the 1.5-approximation heuristic of Christofides. For the asymetric TSP (where we have a directed graph, but the triangle inequality still holds), the best approximation achieved is O(log n). However, there is a natural LP relaxation by Held and Karp. It has been conjectured that the optimum of this LP is within a factor of 3/4 of the optimum TSP cost (even for the directed case).
This is a big topic, perhaps David Williamson's master thesis can serve as an introduction.

Embedding of metric spaces

Bartal's result that an arbitrary finite metric can be approximated by a distribution over tree metrics. On Approximating Arbitrary Metrics by Tree Metrics
Moses Charikar et al. improve the result by showing that O(n log n) are enough. Approximating a Finite Metric by a Small Number of Tree Metrics
A tight bound on approximating arbitrary metrics by tree metrics

Game Theory

Selfish routing. T. Roughgarden and E. Tardos: How Bad is Selfish Routing?

Miscellaneous

  1. The Lazy Bureaucrat Scheduling Problem
  2. Quasiconvex Analysis of Backtracking Algorithms
  3. Memory Efficient Arithmetic
  4. Approximate Frequency Counts over Data Streams, VLDB 2002