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


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


The class is scheduled for Wednesdays 3-6 in Roseburgh (RS) 310. Please send any comments or questions to the instructor:

Announcements will be placed here as appopriate.


COURSE DESCRIPTION:

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. 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 course will be based on a textbook that is now being written by Denis Pankratov and myself. 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, I strongly suggest a course similar to our undergraduate algorithms course CSC373.

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:

  • 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

  • Lecture slides will be posted here. I will try to post a preliminary version of the slides before the lecture and then a "final" version following the lecture.
  • 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
  • Ben-David et al request answer games
  • Fleischer and Wahl current best makespan for m large with good historical review of makespan
  • Yao bin packing
  • Balogh et al current best bin packing with good historical review of bin packing
  • El-Yaniv et al time series and on-way trading
  • The seminal KVV paper regarding online bipartite matching and the Ranking algorithm.
  • The 1996 survey by Hal Kierstead concerning online graph coloring. This is a not so recent survey. Kierstead survey.
  • Relatively recent paper by Albers and Schraink providing randomized lower bounds for online coloring.
  • The 2013 survey by Aranyak Mehta concerning bipartite matching Online Matching and Adllocation. This is an excellent survey but of course not totally up to date. Mehta survey.
  • The pricing online decisions paper. I think this is an interesting perspective that should be applied more widely in online algorithms. pricing online decisions.
  • An economic interpretation for the Ranking algorithm for the BMM problem. economic view of Ranking
  • Boyar et al survey for online algorithms withj advice. online with advice
  • Here are 2009 Lecture Notes on Data Stream Algorithms by Amit Chakrabarti. He has more recent 2011 and 2015 courses on Data Stream Algorithms. Data Stream Lecture Notes
  • The following paper is an experimental study of some algorithms for the BMM problem. The paper contains an informal desrciption of many of the i.i.d. algorithms for the BMM problem. Experimental paper concerning algorithms for the BMM problem..
    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.
  • Here is a draft (posted November 13) of the index and first 16 chapters of the text but missing almost all of chapters 12-15. All of the chapters are still being written so 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 first 12 chapter plus chapter 16.