Stochastic Combinatorial Optimization (Winter 2009)

This page contains the course materials for Stochastic Combinatorial Optimization, ORI 397.

In the sidebar, you will find the class schedule.  The schedule includes lectures and project due dates.  Click on a due date to recieve a description of what materials are due on that day.  Similarly, you can click on a lecture to receive more information on the content of the lecture for that day.  Lecture descriptions will be updated as the lectures get closer.

Student Projects and Lecture Notes

Lecture Contents

  1. Review of NP.  Introduction to approximation algorithms.  Vertex Cover.  General TSP.  Metric TSP. (pdf)
  2. Cardinality Max Cut.  Weighted Max Cut.  FPTAS for Knapsack. (pdf)
  3. Strong NP hardness and FPTAS.  Greedy Set Cover.  Set Cover via Dual Fitting. (pdf)
  4. Reinterpret Dual Fitting as greedy.  Rounding and Randomized Rounding for Set Cover. (pdf)
  5. 1/2-integrality of Vertex Cover.  Relaxed Complimentary Slackness.  LP algs as combinatorial algs. (pdf)
  6. Review of Ellipsoid method.  Min Cut.  k-Hurdle.  Multiway Cut. (pdf)
  7. Multiway Cut by Distance Rounding.  Multicut in general graphs. (pdf)
  8. Max Cut via Semidefinite Programming. (pdf)
  9. Intro to Online Algorithms.  List Access via Potential Function Argument.  Compression. (pdf)
  10. Paging.  Longest Forward Distance is optimal.  Resource Augmentation. (pdf)
  11. Marking algorithms, Least Recently Used is competitive.  Caching.  The Landlord algorithm. (pdf)
  12. Online scheduling.  Greedy online algorithm for permanent jobs and jobs with processing times. (pdf)
  13. Deterministic lower bound and Greedy on restricted machines.  Minimizing weighted completion time. (pdf)
  14. Approximations for minimizing wtd. completion time: release times, precedence, parallel machines. (pdf)
  15. Online scheduling algorithms constructed from approximation algorithms. (pdf)
  16. m-Knapsacks approximation.  Predicting on expert advice and weighted majority. (pdf)
  17. Intro to regret minimization.  Randomized Weighted Majority for minimization and maximization. (pdf)
  18. Randomized Weighted Majority for arbitrary gains.  Plotkin, Shmoys, Tardos feasibility approach. (pdf)
  19. Adversarial Bandit Problem and the Exponential Weight algorithm. (pdf)
  20. Online Convex Optimization.  Overview of regret minimization. (pdf)
  21. Online Convex Optimization using expected gradient and one point gradient estimates. (pdf)
  22. Bandit Online Convex Optimization. (pdf)
  23. Talk by Tara Rengarajan on Probabilistically Constrained Programming.
  24. Talk by Siddhartha Banerjee on Resource Allocation in Wireless Networks.
  25. Talk by Jing Zan on Queueing Systems with Random Parameters.
  26. Talk by Inderjeet Singh on Preventative Maintenance Scheduling for Systems with Interactions.
  27. Talk by Harish Ganapathy on Limited Feedback in Wireless Networks.
  28. Talk by Ashton Mozano on New Product Development.
  29. Targeted epidemic intervention.

Approximation Algorithms Resources

These are all useful and presented in no particular order.  They often contain alternate presentations of the same algorithms/techniques.  Looking through these resources might be useful to you in the first part of the course.

Online Algorithms Resources

Again, these are all useful.

Regret Minimization

All excellent resources:

This is a completed course

Related Pages

© Copyright 2004-2019 - Ned Dimitrov