RANDOMIZATION AND OPTIMIZATION

period IV (March-May), 2001

Course content: This is meant to be a research level Ph.D. course about recent algorithmic advances in optimization that were obtained by the introduction of randomization techniques. It can be taken as either a follow-up to or in conjunction with (or both!) Olle Häggström's course on randomised algorithms which is offered again this study period. The course will concentrate on the fundamental probabilistic techniques behind the advances, and will illustrate them by applications to central problems in graph and network optimization and linear programming. The main themes to be covered in the course are: The use of randomization together with linear programming(LP) as a black box for the solution of hard combinatorial optimization problems. Some ubiquitous tools (concentration of measure and the Lovasz Local Lemma) for the analysis of randomized algorithms. The use of randomization in geometric settings (embeddings and projections) and applications to combinatorial optimization. Random sampling as a powerful and versatile tool in developing simple and efficient algorithms for optmization problems, illustrated in particular, for spanning trees, LP and LP-type problems. Simple and efficient algorithms inspired by simulated-annealing for clustering and classification problems. An integral part of the course consists of a project, where the students have the opportunity to apply the above to some concrete application, or to deepen their theoretical knowledge in some specific direction (or both!).

Schedule: Lectures take place in room S4 (in Matematiskt centrum), on

• Tuesdays, 13-15, and
• Thursdays,15-17.

There are no lectures during the two weeks surrounding Easter (April 9-20).

Here is a more detailed schedule of the lectures; changes may appear.

Day	Date	Topic
Tuesday	March 13	Randomized Rounding
Thursday	March 15	Randomized Rounding (cont'd)
Tuesday	March 20	Concentration of Measure
Thursday	March 22	Lovasz Local Lemma, Primal-Dual method (Algorithms Research Seminar)
Tuesday	March 27	Johnson-Lindenstrauss Lemma
Thursday	March 29	Primal-Dual Method (Algorithms Research Seminar)
Tuesday	April 3	Sparsest Cut and Graph Embeddings
Thursday	April 5	Graph Embeddings: The Bourgain Embedding.
April 9-20: Easter break.
Tuesday	April 24	Random Sampling I: Spanning Trees
Thursday	April 26	Random Sampling II: LP
Wednesday	May 2	Abstract LP-type problems .
Thursday	May 3	Metropolis algorithms for graph bisection.
Tuesday	May 8	Metropolis algorithms for bisection (cont'd)
Thursday	May 17	Frederik, Sverker, Katarina, Peter

Prerequisites: There are strictly speaking no prerequisites to this course other than a broad acquaintance with algorithms and elementary discrete mathematics including graph theoretical concepts and notation and basics of discrete probability (random variables, expectation, linearity of expectation). In particular, no knowledge is assumed about linear programming and everything needed will be developed from scratch.

Literature:

• Textbooks
  • The standard textbook R. Motwani and P. Raghavan, Randomized Algorithms (Cambridge University Press, 1995), contains some of this material and is highly recommended. It's referred to below as "Motwani and Raghavan".It can be ordered at bol.com. If you have access to MathSciNet, then you may click here to see a review of the book.
    
    
  • A wonderful book that has already become a classic is The Probabilistic Method , by Noga Alon and Joel Spencer, in its second edition now. It's referred to below as "Alon and Spencer".
    
    
  • A beautiful new book by Bernard Chazelle, The Discrepancy Method: Randomness and Complexity , Cambridge University Press 2000. Take a look at the contents.
    
    
  • Vijay Vazirani , Approximation Algorithms (forthcoming Springer-Verlag 2001). Download your copy from his homepage for free now!
    
    
  • Approximation algorithms for NP-hard problems , Dorit Hochbaum (ed). Some excellent chapters.
• Surveys
  • Randomization in Graph Optimization Problems: A Survey by D. Karger.
  • Computing Near-Optimal Solutions to Combinatorial Optimization Problems by D. Shmoys. Excellent survey!
• Randomized Rounding
  • D. Bertsimas and R. Vohra, "Rounding Algorithms for Covering Problems", Mathematical Programming , 80 (1998) pp. 63-89.
  • This is a good survey on randomised rounding by Aravind Srinivasan.
  • Section 4.3 in Motwani and Raghavan gives an application of VLSI routing via randomized rounding .
  • For derandomization via the Method of Conditional Expectation, see section 15.1 of Alon and Spencer, section 1.1 of Chazelle and for a more elaborate treatment, section 4.2 of Srinivasan's survey.
• Concentration of Measure
  • Chapter 4 in Motwani and Raghavan.
  • Download draft of a book in progress.
• Johnson-Lindenstrauss Lemma
  • An Elementary Proof of the Johnson-Lindenstrauss Lemma by S. Dasgupta and A. Gupta.
  • Johnson-Lindenstrauss Embedding , notes by L. Schulman.
  • Johnson-Lindenstrauss Embedding , notes by L. Schulman.
• Lovasz Local Lemma
  • Chapter 5 in Alon and Spencer.
  • Section 5.5 in Motwani and Raghavan.
  • Packet-routing and Job-shop scheduling in O(dilation+congestion) steps by T. Leighton, B. Maggs and S. Rao. The seminal paper.
  • A natural and useful extension of the Local Lemma by Aravind Srinivasan. Can you find a different proof?
• Sparsest Cuts and Graph Embeddings
  • Chapter 18 in Vazirani's notes.
  • Cut Problems and their Application to Divide-and-Conquer Algorithms by D. Shmoys. Excellent chapter in the book by Hochbaum.
  • Embedding finite metric spaces into Euclidean spaces a chapter in a forthcoming book by Jiri Matousek. Highly recommended!
  • The Geometry of Graphs and Some of its Algorithmic Applications by N. Linial, E. London and Y. Rabinovitch. The original article, somewhat confusing ...
• Random Sampling: Spanning Trees
  • A Simple Sampling Lemma: Analysis and Applications in Geometric Optimization by B. Gaertner and E. Welzl.
  • Section 10.3 in Motwani and Raghavan.
  • A Randomised Linear Time Algorithm to find Minimum Spanning Trees by D. Karger, P. Klein and R. Tarjan.
  • See Chapter 11 in Chazelle's book for the tortuous attempts to get a matching deterministic algorithm. It fails: the best deterministic algorithm runs in time O(m \alpha(m,n)), where \alpha is the inverse Ackermann function. It is also a lot more complicated!
• Random Sampling: LP and abstract LP
  • Section 9.10 in Motwani and Raghavan.
  • A Survey on Linear Programming in Sub-Exponential Time by M. Goldwasser.
  • Randomized Algorithms for Linear Programming by A. Nayak and Zendong, a term paper for a course, a model to be followed for this course!
  • Linear programming: Randomization and Abstract Frameworks by B. Gaertner and E. Welzl.
  • Randomization and Abstraction: Useful Tools for Optimization slides from a minicourse at BRICS by B. Gaertner.
• Simulated Annealing and Metropolis-type algorithms for graph bisection.
  • The Metropolis Algorithm for Graph Bisection by M. Jerrum and G. Sorkin.
  • Algorithms for graph bisection on the planted partition model by A. Condon and R. Karp.
  • journal version of the above which just appeared!

• Written and oral presentation of a project, and
• a written exam on the material covered in the lectures. This will be a take-home exam for which you can consult books and notes. The time allowed will be roughly one week. Here is the exam ! Here are the solutions !

Project: An integral part of the course is to do a project, either individually or in groups of 2-3 students. Projects can be chosen from a list which will appear here shortly, but suggestions for other projects are also welcome. Each student is required to have selected a project (after consulting me) no later than the 3rd week of the course (March 26-30).

Project Topics

1. Derandomization via Small Sample Spaces This is an alternative method of derandomization. Study the papers and apply the method to derandomizing the randomized rounding algorithms for covering problems discussed in class. A nice set of lecture notes by Mike Luby and Avi Wigderson is Pairwise Independence and Derandomization . A compact paper with several constructions of small spaces is Alon et al .
2. Extending the Bourgain Embedding Study this tour-de-force paper involving far-reaching generalization of the Bourgain embedding: Approximating the bandwidth via volume-preserving embeddings by Urie Feige.
3. Approximations by Tree Metrics Study the two appers of Y. Bartal that provide a very useful tool for approximation algorithms. Probabilistic Approximation of Metric Spaces and its Algorithmic Applications and Approximating arbitrary metrics by tree metrics .
4. JL Lemma applied to Learning An application of the JL-Lemma to learning mixtures of distributions: Learning Mixtures of Arbitrary Gaussians by S. Dasgupta.
5. JL and Latent Semantic Indexing (LSI) LSI is a widely used method in information retrieval. An informative site is here and there is an active local Chalmers group . Explore applications of the JL Lemma in their work.
6. Clustering on the Web Check out this site for a clustering algorithm for web-queries: Manjara . Explore the applicability of simple metropolis-type algorithms in this context. Here are two more papers on clustering: spectral methods and sampling and isometries method .
7. Fingerprinting for Persistence on the Web (Thanks to Reiner Hahnle for this suggestion.) You've probably also encountered this annoying problem: you've bookmarked an important page, and later when you point your browser there, you find that it's not there anymore. Actually it's unlikely to have vanished into thin air; more likely there was some local reorgaization of links. Now, your problem is to locate the page again. One approach to do it to to keep not only the link itself but also a "fingerprint" of the page so that in such a situation, you can use the fingerprint to relocate the page. Typically, you can supply it to a search engine like Google and retrieve a bunch of pages and rank them by similarity to the original page. Explore the vector space representation ideas of LSI in this context. See also section 7.5 in Raghavan and Motwani. Also check out: Compaq's research on this. Here is a paper .
8. Classification Problems Here is a paper on Approximation algorithms for classification problems . Develop a scenario where Metropolis-type algorithms can be useful in this context.
9. Geometrical embeddings in Computational Biology Here is a paper on phylogenetic trees constructed using geometrical embeddings of graphs.
10. Random Sampling in Computational Geometry Computational Geometry has seen some of the most striuking applications of the random sampling paradigm. Study the application of random sampling to central problems in computational geometry like convex hulls, line arrangements, trapezoidal decompositions, triangulations etc. You can read about them in the following textbooks:
    • M. de Berg, M. van Krevald, M. Overmars and O. Schwarzkopf, Computational Geomtery: Algorithms and Applications , second edition, Springer-Verlag 1998.
    • K. Mulmuley, Computational Geometry: An Introduction through Randomized Algorithms , Prentice Hall 1995.
    Implement a simple randomized algorithm for convex hull in two or three dimensions.
11. Abstract LP in Software Explore the software package for smallest enclosing ball.
12. Randomized Simplex One of the most fascinating and challenging open problems in optimization is the analysis of the Simplex algorithm. While known to be exponential in the worst case, it behaves remarkably well in practice. Gil Kalai came up with two simple randomized pivoting rules for Simplex that give provably sub-exponential algorithms, see his paper . An analysis of randomized Simplex on Klee-Minty cubes shows an exponential improvement over the determinsitic version (for which it is famously the worst case). Conduct experiments to see how well this analysis is borne out in practice.