CSC2421 Topics in Algorithms: Online and other Myopic Algorithms (Fall 2025)

This page will provide WWW access to various documents concerning CSC2421. Announcements will also be made on this page and on Quercus.

The class is scheduled for Wednesdays, 12-2. NOTE: Change of rooms. We will now be meeting in HS 696 and not in OISE. Please send any comments or questions to the instructor:
Announcements will be placed here as appopriate.

COURSE DESCRIPTION:

While the title "Online and Other Myopic Algorithms" may seem very specialized, the course should be accessible to any CS student and also serves as a partial introduction to many of the topics in CSC2420. The course will be based on a text (co-authored with Denis Pankratov) that hopefully will completed by summer 2026. It is a reasonably self-contained text for anyone who has the equivalent of our CSC373 undergraduate course.

The adjective ``myopic'' implies algorithms where we do not see all the input items in advance; that is, after processing the first i items we have limited knowlegde about item i+1 and other future items. We will take a broad view of this term and (for example) will include (for example) algorithms that have some limited ability to change past decisions and we will consider both worst case and stochastic inputs.

The topic of online myopic algorithms is of growing interest due to the increasing number of applications. We will consider various applications such auctions, fair division, scheduling, max-sat and graph algorithms, as well as some abstract algorithmic frameworks such as the k-server problem.

A preliminary table of contents and bibligography for the text is provided here. Like the text it will be constantly changing.

  • Draft of table of contents.
  • Draft of the text bibliography.

    • There are a number of excellent undergraduate texts (e.g. "Algorithm Design" by Jon Kleinberg and Eva Tardos; "Introduction to Algorithms" by Corman, Leiserson, Rivest and Stein; ``Algorithmics: Theory and Practice" by Brassard and Bratley; and "Algorithms" by DsGupta, Papadimitriou and U. Vazirani) that cover the standard topics and include some advanced material. There are also a number of texts on somewhat specialized topics (e.g. "Approximation Algorithms" by V. Vazirani; "A First Course in Combinatorial Optimization", by James Lee; and "Randomized Algorithms" by Motwani and Raghaven). There are also many web accessible courses that indicate the diversity of topics taught in graduate algorithms courses. For example, you may want to consider the following sources:

  • My Spring 2021 course
  • My Spring 2022 course
  • The last version of my CSC2420 course.
  • Tom Roughgarden Stanford Lectures
  • Princeton University CS521
  • University of Washington CSE 521
  • University of Washington CSE 522
  • Cornell University CSC6820
  • CMU 451/651
  • Nikhil Devanur Online Course
  • Avner Magen LP and SDP Course

    • Slides for the course will appear here. These slides will amplify what is in the text chapters.
  • Week 1 Organization and Motivating the course. The text chapters. Variants of the online model.
  • Week 2 More motivation for the course. Graham's online and offline greedy makespan algorithms for the identical machines model. Surprising anomoloies. Three other makespan models: the uniformly related, restricted and unrelated models
  • Week 3 Greedy and online algorithms for the general and proportional knapsaack problems. The priority model for greedy and myopic algorithms. Extensions of the priority model.
  • Week 4 David Zhang's slides for his guest presentation on randomness extraction and the simulation of 1-bit barely random online algorithms by deterministic ROM algorithms.
  • Week 5 Followup on David Zhang's class. Extensions of online and priority algorithms, randomized algorithms for max-sat, de-randomizing the max-sat algorithm into a 2 pass online algorithm, experimental results for max-sat.
  • Week 6 Suggestions for projects (with resspect to chapters 1-9 + chapter 11. The deterministic two-sided online greedys algorithm for non-monotone submodualr maximniation. and the natural randomization of that deterministic algorithm. De-randimizing thhe two-sided algorithm into a polynomial width 2n levelled DAG. The min cost metric matching problem for arbitrary metric spaces and for the line metric space.
  • Week 7 More suggestions for projects. The robust min cost colouring algorithm. Input models for graph problems. Vertex cover in the edge model. Graph colouring in the online vertex adjency input model. A negative result for arbitrary graphs. An optimal competitive ratio for trees.

    • Assignments will be posted here. There will three assignments including a mini-project/presentation. I will accept individual submissions as well as subissions from pairs of students. All projects need to be approved in advance and I will consider project proposals at any time. The presentations will take place in the last few weeks of the course. The written projects should not no longer than 10 pages. All assignments should be submitted on Markus.

  • Assignment 1
    • Additional papers/slides will be posted here.
  • Probability Primer
  • Kim Larsen slides for online algorithms
  • Buchbinder and Naor 2017 monograph on the primal dual method for online algorithms
  • Boyar et al survey on trusted advice
  • Mitzenmacher and Vassilvitskii survey on untrusted advice