Online Algorithms
& Online Rounding: Recent Progress
Organizers:
Zhiyi Huang, University of Hong Kong
David Wajc, Technion — Israel Institute of Technology
Abstract:
Sequential decision-making under uncertainty, as captured by online algorithms, has seen tremendous advances in recent years. The area has seen breakthrough algorithms for matching, budgeted allocation (Adwords), and edge coloring, among others, as well as recent progress in active sub-areas, such as online selection problems, and algorithms with advice. Common to many such recent developments is the relax-and-round framework:
(1) relax the problem, and approximate this relaxation.
(2) round the solution.
Step (1) is relatively well-understood; while still far from trivial, a generic approach for designing and analyzing online fractional algorithms is given by the online primal-dual schema.[1] Step (2) imposes more challenges; while in offline settings, decades of research have provided a wealth of powerful general rounding tools,[2] in online settings, the search for general rounding tools has much more room for growth. Progress on this second objective underlies many recent advances in the area of online algorithms, and has informed developments in other areas.
The workshop will include overviews of some exciting recent developments in online algorithms, with a particular focus on their core key ingredient: online rounding. The talks will overview online rounding approaches, including online oblivious rounding, online correlated selection, and online contention resolution schemes. Contrasts between these approaches and applications will be highlighted, from numerous breakthroughs in classic online algorithms, to applications in economics and computation, algorithms with predictions, and all the way back to offline algorithms. The objective of the workshop is to highlight the powerful underlying techniques and exciting developments to the broader theory community, with the hope of fostering a further fruitful crossover of techniques between algorithms researchers in different areas.
Workshop format: Three days of 75-minute overview talks and one day with 3 invited talks.
Day 1 (Nov 6): mini bootcamp, online oblivious rounding [slides] David Wajc, Technion
Mini bootcamp: Workshop overview; Online primal-dual; Offline rounding;
Online oblivious rounding schemes (OORS)
Applications:
Online edge-coloring
Barely-random algorithms
Semi-online correlated selection
Approximating the optimum online
________________________________________________________________________
Day 2 (Nov 7): Online correlated selection (OCS) [slides] Zhiyi Huang, University of Hong Kong
Applications:
Online edge-weighted matching (a.k.a., Display Ads)
Online budgeted allocation (a.k.a., AdWords)
Online stochastic matching
Online allocation of reusable resources
Class fairness in online matching
________________________________________________________________________
Day 3 (Nov 8): Online contention resolution schemes (OCRS) [slides] Sahil Singla, Georgia Tech
Applications:
Online Bayesian selection
Oblivious posted price mechanisms
Stochastic probing
Algorithmic delegation
Matroid secretary
________________________________________________________________________
Day 4 (Nov 9): Invited talks
Will Ma, Columbia University
“Order-optimal Correlated Rounding for Fulfilling Multi-item E-commerce Orders” EC23 [slides]
Sungjin Im, UC Merced
“Improved Approximations for Unrelated Machine Scheduling” SODA23 [slides]
Shi Li, Nanjing University
“Online unrelated machine load balancing with predictions revisited” ICML21 [slides]
________________________________________________________________________
Relevant talks online:
[1] The online primal-dual schema (relax)
“Competitive Analysis of Online Algorithms” Part I, Part II. Seffi Naor @ Simons.
[2] (Offline) dependent rounding (round)
“A survey of dependent rounding.” Aravind Srinivasan @ Simons.