A BRICS Mini-Course
May 18, 20 and 26, June 7, 14 and 16, 1999
Lectures by
Devdatt Dubhashi, dubhashi@cse.iitd.ernet.in
Indian Institute of Technology, Delhi, India
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:
Randomization:
There will of course be a lot interaction between the two series. Active participation from the audience will be expected.
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.
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
In the first part, I'll introduce an approach to the metric Steiner tree problem due to Rajagopalan and Vazirani:
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?
I'll discuss two powerful powerful tools for the analysis of randomized algorithms:
I'll discuss two powerful inequalities in the setting of dependency graphs that are extremely useful tools for the analysis of randomized algorithms:
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.
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.