CSC2421 Topics in Algorithms: Online and other Myopic Algorithms (Winter/Spring 2021)

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

In case there are any students who wanted to attend both this course and Nisarg Shah's course (Thursday 1-3), I have moved the 2421 course time to Thursday, 4-6. I will post the zoom link for the January 21 class on Quercus around 3:45 on the 21st. If you are not enrolled but would like to join the clsss (even if just to audit) please contact me at "bor atsymbol cs.toronto.edu". If you think you are enrolled but did not get the annoucement with the zook link then please contact me. For those joining the clsss today, you may want to download the index and chapters 1-3 of the text. See the link at the bottom of this web page.
The class is now scheduled for Thursdays 4-6. Unfortunatley therev are two sections of CSC2421, this course and the one presented by Professor Sushant Sachdeva. I will try to see if we can fix this ambiguity as it means students can only take one section with the same number. For the foreseeable future the class will be held remotely. I plan to use zoom but we could alternatively use BbCollbaorate. I will post the zoom link on this web page and BbCollaborate for the initial meeting. Hopefully we will be able to meet in person at some time but at the moment it does not look good for meeting in person. We begin Tuesday, January 12. It would be very helpful for me to have an idea of those who are considering auditing or taking the course for credit. We will run the curse mainly as a semminar style course with students presenting papers and topics. Please send any comments or questions to the instructor:
Announcements will be placed here as appopriate.

COURSE DESCRIPTION (mainly copied from the 2421f19 course):

In a seminal 1985 paper, Sleator and Tarjan argued for a worst case analysis of online algorithms such as paging and list accessing. This became known as competitive analysis. Not surprisingly, such worst analysis was already present in earlier works for example by Graham and Yao for scheduling problems and also in topics relating to the "secretary problem". Since these earlier works, there has been a continuing and growing interest in online algorithms, in terms of applications (eg online advertising and other auctions, graph colouring and matching, maximum satisfiability, etc.), in terms of alternative online models (eg small space streaming, sequential and parallel streams), extensions to the basic online model (revocable decisions, greedy-like algorithms), and in terms of alternatives to the competitive analysis framework (eg, a return to stochastic input models). This topic is part of recent interest within theoretical computer science that emphasizes "conceptually simple algorithms" (e.g., the SOSA conference). A preliminary table of contents is provided below. In terms of a prerequisite,

The course is suitable for any graduate student who has the prerequistie which is the equivaslent of our undergraduate algorithms course CSC373. The course is a foundational course but can provide research ideas for those with some intertest in theoretical CS. While the topic "Online and other myopic algorithms" is indeed focused, these algorithms connect with all the main topics in algorithm design.

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 previous CSC2421 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 spring 2021 term will appear here. These slides will mainly be used to amplify what is in the text chapters.
  • Week 1 Organization and Motivating the course. Online and myopic algorithms. Variants of the online model. Graham's online and "semi-online" greedy makespan algorithms for the uniform machine model.
  • Week 2 Overview of the materal in Chapters 1 and 2. Chapter 1: history, ski rental problem, line search problem, paging problem. Overview of the materal in Chapters 1 and 2. Chapter 1: history, ski rental problem, line search problem, paging problem. Chapter 2: request-answer games, definition of competitive analysis, bin packing, time-series search, and one-way trading problems.
  • Week 3 Overview of the materal in Chapters 2 and 3. We discuss bin packing in a little more detail. The Harmonic algorithm. Overview of material in Chapter 3. Differeent adversaries for randomized algorithms. Rendomized algorithms for proportioanl knapsack, time seriees, paging.
  • Week 4 We continue doing a tour of the text chapters. This week we did a quick tour of Chapters 4,5,6,7 and Chapter 20 given its relation to bipartitie matching as first considered in Chapter 5.
  • Week 5 We finished doing a tour of the text chapters. Namely, we did chapters 8 through 23
  • In week 6, we had two student presentations. Here are the slides for Koosha Jaferiann's overview of min cost and max matching. And here are the slides for Xiaoxu Guo's overview of paging.
  • In week 7, we had three student presentations. Here are the slides for Koko Nanaah JI's overview of streaming. And here the slides for Alex Cann's overview of temporrary jobs and the makespan problem. And here the slides for Jinman Zhao's overview of online graph coloring.
  • Week 8 We presented results for the secretary problem, prophet inequalities and the prophet secretary problem.
  • In week 9, we had student presentations on the prinal dual method for paging and the min cost matching problem. Here are the slides for Koosha Jaferiann's overview of min cost matching. And here are the slides for Xiaoxu Guo's overview of the primal dual method for paging.
  • In week 10, we started with a student presentation regarding online graph coloring. And here the slides for Jinman Zhao's presentation of online coloring of chordal and general graphs. We then continued with a discussion of multi item secretary and prophet secretaries. Week 10 slides
  • In week 11, we had two student presentation. Here are the slides for Koko Nanahji's presentation of streaming algorithms for approximate counting. Here are Alex Cann's slides for the presentation of scheduling temporary jobs in the related and restricted machines model.
  • Week 12 We presented results for the secretary matching problem, online algorithms with ML predictions, and probing problems.

    As this will be mainly a seminar style course we will not have many slides but here are some slides from the 2421f19 course.
  • Week 1 Motivating the course and starting to introduce basic combinatorial paradigms. Online algorithms, competitive analysis, greedy, partial enumeration greedy, ski rental, makespan, bin packing
  • Week 2 Comments on bin packing, time series and one-way trading problems, randomized online algorithms and types of adversaries, examples where randomization helps and doesn't help, Yao principle, paging.
  • Week 3 The potential function method, list accesssing, k-server lower bound by averaging technique, k-server on the line and a tree metric, weighted paging, metrical task systems, makespan on other machine mlodels.
  • Week 4 Online graph optimization problems. Input representations. Online hardness of approximation for many graph problems. Biprtite max matching. The Ranking algorithm. Online graph coloring.
  • Week 5 The Max-Sat problem. Input representations for Max-Sat. The naive randomize algorithm. De-randomization by the method of conditional expectations. Johnson's deterministic algorithm. A randomized 3/4 randomized competitive ratio. Brief discussion of the unconditional maximzation of a non monotone submodular function.
  • Week 6 The primal dual framework for online algorithms. The offline and online set cover problem. The fractional primal dual algorithm, and its use inndeveloping amdomized and deterministic integral solutions. The makespan problem for the unrelated machines model. The primal dual analysis of the Ranking algorithm for the unweighted and offline vertex weighted bipartite matching problem.
  • Week 7 An economic view of online algorithms. Incentivizing online agents to make decisions so as to lead to better social welfare objectives. The k-server problem on rthe line, and the parking problem. An economic interpretation of the primal dual algorithm for bipartite mac matching (without stating the LP). Online algorithms with advice. The tape model and various positive and negative results analyzing the number of advice bits to acheive certain competitive ratio.
  • Week 8 The streaming model. Some simple deterministic streaming algorithms. Estinating the second frequency moment. Turnstile input models.
  • Week 9 The first half of the lecture was given by Kayman Brusse on the online with advice model. The second half was the strat of a dicsussion on stochastic inputs. The ROM model. The secretary problem. Genertalizing the secretary result to bipartite matching in the ROM model and selecting a set of candidates subject to a matroid constraint. ROM results imply i.i.d. results. The i.i.d result for the BMM problem.
  • Week 10 The first half of the lecture was given by Carolyn Hu on the material in Chapter 6 ands mainly on algorithms for Max-Sat. We reviewed the known i.i.d. input model and the Felmdan algorithm. We stated what is now known abojut the BMM problem in the known i.i.d. model. We next considered the prophet inequalities problem and the optimal stopping rule yield a 1/2 competitive ratio. We introduced stochastic probing and the stochastic rewards problem and what is an appropriate benchmark.
  • Week 11 The first half of the lecture was given by Gregory Rosenthal who discussed dynamic graph algorithms. We returned to the stochastic rewards problem and presented the Brubach et al result for stochastic rewards with patience. We concluded the course with a quick mention of some more recent online studies. This inculded the online Pandora's box problem, online matching tasks to experts, the k-taxi problem, and finally the adwords and display ads problems.

    • Assignments will be posted here.

    Additional papers/slides will be posted here. I will post papers more or less in chronological order of the material in the text and course.
  • Probability Primer
  • Kim Larsen slides for online algorithms
  • Buchbinder and Naor 2017 monograph on the lrimal dual method for online algorithms
  • Boyar et al survey on trusted advice
  • Mitzenmacher and Vassilvitskii survey on untrusted advice
    • Preliminary versions of some chapters from our new ``Online Algorithms'' text will be posted here. We are just beginning this text so there are bound to be mistakes and incomplete references. We welcome any comments.
  • Here is the current bibliography (posted September 12) of the text. Like the text it will be constantly changing. Draft of the text bibliography.
    • All of the chapters are still being written. Some chapters do not yet exist. In any existing chapters there are missing results, missing references and in general, one should look up the original sources to be sure of anything. We will release chapters as we cover material in the course. Draft of index and chapters 1-3.