BRICS · Contents · Programme · References

Randomization and Approximation Algorithms in Combinatorial Optimization

A BRICS Mini-Course
May 18, 20 and 26, June 7, 14 and 16, 1999

Lectures by
Devdatt Dubhashi,
Indian Institute of Technology, Delhi, India

Course Contents

Devdatt Dubhashi will be visiting BRICS in the period May 17-July 7, 1999. While at BRICS, Devdatt Dubhashi will run a regular lecture and seminar series. The first two lectures will be an introduction to both series.

Lecture Series

This will be a series of lectures to learn about topics related to randomization and approximation algorithms in combinatorial optimization. Topics on the top of my list presently are:

Seminar Series

This will be a problem oriented seminar whose aim will be to focus on specific problems and their solution. The goal will be to produce research papers! Problems on the top of my list:

Approximation algorithms:


There will of course be a lot interaction between the two series. Active participation from the audience will be expected.


Tuesday May 18, 1999, 15:15-17:00 in Auditorium D4

Introduction to the Lecture Series

This lecture series will cover topics on Combinatorial Optmization centered around Linear Programming based algorithms. An overview of the topics to be covered in the lecture series will be given: LP Duality, Oriented Matroids, Randomized Rounding, Goemans-Williamson Primal Dual Framework.

Any of the references may be consulted for more information.

Thursday May 20, 1999, 15:15-17:00 in Auditorium D4

Introduction to the Problems Series

This series will concentrate on solving important open problems that can be tackled by methods treated in the Lecture series. An introduction to the problems I have in mind will be given: Approximation algorithms: Steiner trees and networks, group Steiner trees, Shallow-light spanning trees. Randomization: Random trees, negative dependence Web algorithms: Data mining, clustering.

The randomised rounding algorithm I mentioned is due to

  • N. Garg, G. Konjevod and R. Ravi: "A polylogarithmic approximation algorithm for the group Steiner tree problem", SODA 1998.

Wednesday May 26, 1999, 10:00-12:00 in Auditorium D4

Open Problems: Steiner Trees and Random Trees

In the first part, I'll introduce an approach to the metric Steiner tree problem due to Rajagopalan and Vazirani:

  • S. Rajagopalan and V. Vazirani, "On the Bidirected Cut Relaxation for the Metric Steiner Tree Problem", STOC 98 (?).

It is based on a old approach of the Master Jack Edmonds and gives a 3/2 approximation for quasi-bipartite graphs i.e. those having no edges between Steiner vertices. The challenge is to extend it to the general case.

In the second part, I'll discuss a fascinating question in randomization: how tall is a random tree?

Monday June 7, 1999, 10:00-12:00 in Colloquium B4

Lecture: Correlation Inequalities

I'll discuss two powerful powerful tools for the analysis of randomized algorithms:

  • FKG Inequality, Holley's inequality and Regression inequalities.
  • Janson's inequality for Poisson approximation.

Monday June 14, 1999, 10:00-12:00 in Colloquium B4

Lecture: Two Inequalities with Dependency Graphs

I'll discuss two powerful inequalities in the setting of dependency graphs that are extremely useful tools for the analysis of randomized algorithms:

  • Janson's inequality (left over from last time).
  • Lovasz Local Lemma.

Wednesday June 16, 1999, 10:00-12:00 in Auditorium D4

Open Problems: Probabilistic Recurrences

Karp introduced probabilistic recurrences as a very useful framework for the analysis of randomised algorithms akin to using usual determinsitic recurrences for deterministic algorithms. He supplies a Master Theorem that can be applied in a cook-book fashion (again parallel to the deterministic case). It works very well with algorithms that generate only one subproblem, but not so well when many subproblems are generated.


There are some excellent surveys on approximation algorithms:

Some excellent textbooks on linear programming are:

An excellent new (slim!) textbook that has appeared is:

Besides these, specific references for each lecture are listed below along with the lecture.