networking theory seminar

Networking theory seminar

About the seminar

Networking theory seminar is a minicourse / research seminar hosted by Maciej Pacut at Communication Technologies Group at University of Vienna. The seminars take place from April 2020.

Public talks

Material overview

The course roughly consists of three parts: The material in this course is based on selected chapters from three books: Additionally, the script by Susanne Albers BRICS lecture notes contains concise overview of some discussed topics.

Part 1: introduction to online algorithms

  1. Introduction to online computation and competitive analysis Examples of online problems: List Access, Splay Tree.
    Competitive analysis.
  2. Metrical Task Systems
    Online problems as Request-Answer Games. Subset of online problems: Metrical Task Systems
  3. Searching for a point on a line.

    Section 2 from Searching in The Plane
    R. Baeza-Yates, J. Culberson, G. Rawlins
    Information and Computation, 1993

    Chapter 9 from BRICS lecture notes.
  4. Online "packing items to containers" problems: Online Bin Packing, Online Knapsack, Online Scheduling
    Cygan Jez
  5. List update: deterministic algorithm Move-To-Front
    (potential function technique)

    Section 2 from Amortized efficiency of list update and paging rules.
    D. Sleator, R. Tarjan
    Communications of the ACM, 1985
  6. List update: randomized algorithms
    (potential function technique)

    Section 2 from Amortized efficiency of list update and paging rules.
    D. Sleator, R. Tarjan
    Communications of the ACM, 1985

    Section 3.1 (only algorithm BIT) from Randomized competitive algorithms for the list update problem
    N. Reingold, J. Westbrook, D. Sleator
    Algorithmica, 1994

    Analysis of combination of BIT and TIMESTAMP from A combined BIT and TIMESTAMP algorithm for the list update problem
    S. Albers, B. von Stengel, R. Werchner
    Information Processing Letters, 1995

    Chapters 1 and 2 from Online Computation and Competitive Analysis. Chapter 5 from BRICS lecture notes.
  7. Online Set Cover via Primal-Dual approach
    Sections 3, 4, 5.1 from Online primal–dual algorithms for covering and packing problems.
    N. Buchbinder, J. Naor
    ESA 2005

    Chapter 4, sections: 4.1, 4.2 (only Algorithm 1), 4.3 and 4.4.1 from the book The Design of Competitive Online Algorithms via a Primal–Dual Approach, Niv Buchbinder and Joseph Naor

Part 2: Online algorithms for networking problems

  1. Caching: deterministic upper and lower bounds, and randomized upper bound
    (phase-based analysis)

    Competitive paging algorithms. A. Fiat, R. Karp, M. Luby, L. McGeoch, D. Sleator, N. Young
    Journal of Algorithms, 1991.

    Possibly the best source is: sections 1.2 and 2.2 from BRICS lecture notes. Also described in various other sources, e.g. chapters 3 and 4 from Online Computation and Competitive Analysis.
  2. Scheduling for identical and related machines.
    (doubling technique)

    As a short warm-up, Section 12.2.1 from Online Computation and Competitive Analysis.

    The main part is section 3.2 from On-Line Routing of Virtual Circuits with Applications to Load Balancing and Machine Scheduling. J. Aspnes, Y. Azar, A. Fiat, S. Plotkin, O. Waarts.
    J. ACM, 1997

    Also described in chapters 12.2.3 from Online Computation and Competitive Analysis. Identical machines described in chapter 8 from BRICS lecture notes.
  3. k-server for trees.

    Section 3 from An Optimal On-line Algorithm for k Servers on Trees
    M. Chrobak , L. Larmore
    SIAM Journal on Computing, 1996

    Section 3.2 from The k-server problem
    E. Koutsoupias
    Computer Science Review, 2009

    Also described in chapter 10.4 from Online Computation and Competitive Analysis.
  4. Distributed file management

    Dynamic Analysis of the Arrow Distributed Protocol
    Maurice Herlihy, Fabian Kuhn, Srikanta Tirthapura, Roger Wattenhofer
    Theory of Computing Systems 2006
  5. Online File Migration

  6. Scheduling in reconfigurable networks

    Primal-dual algorithm and Yao's principle.
    Scheduling for Weighted Flow and Completion Times in Reconfigurable Networks
    Michael Dinitz and Benjamin Moseley
  7. Online load-balancing

    Yossi Azar
  8. Online Scheduling in Flowtime Minimization

    Nikhil Bansal, Bouke Cloostermans: Minimizing Maximum Flow-Time on Related Machines, APPROX 2015
  9. ReNets
  10. Ski Rental with application to networking systems
  11. Online buffer reordering
  12. Online routing

    Variants: knapsack-type of routing (call admission) and scheduling-type of routing (virtual circuits routing)
  13. Online matching

    AdWords and generalized online matching
    A. Mehta, A. Saberi, U. Vazirani, V. Vazirani
    Journal of ACM 2008
  14. Online Graph Partitioning and Online Rematching

Part 3: Beyond Worst-Case Analysis

  1. Virtual input-output queues under speedup (Resource augmentation)
  2. Caching: competitive ratio under resource augmentation results
  3. Caching: Young's loose competitiveness
  4. Stochastic analysis: Valiant routing
  5. Selfish Routing
  6. Caching: access graph
  7. Caching: diffuse adversaries
  8. Caching: expert advice
  9. Caching and List Access: locality in the input
  10. The Secretary Problem: Random Arrival Order model
  11. Lookahead

Further reading

Further topics from online algorithms (under construction)