Date: July 10, 2023
Venue: Seminar Room 1+2, HNF (Heinz Nixdorf MuseumsForum)
Workshop Scope
Online algorithms make irrevocable decisions for an initially unknown input that is revealed sequentially. The goal is to achieve a good competitive performance in comparison to an offline optimal algorithm that can access the entire input in advance. Online algorithms have been intensively studied in recent years and new breakthrough results have been achieved. Further, new models have been proposed that relax the overly pessimistic assumption of not having any prior knowledge about future requests in different ways. Such modern developments allow one to go beyond traditional worst-case competitive analysis and breach pathological impossibility results. Such new trends include (not exclusively):
– Online algorithms with random order arrivals,
– Online algorithms with advice extract a given amount of information about inputs,
– Online learning algorithms iterate multiple rounds,
– Semi-online algorithms assume that some advance information about certain aspects of the input is available,
– Online algorithms with explorable uncertainty execute queries or tests to obtain information about uncertain inputs,
– Learning-augmented online algorithms have access to (machine-learned) predictions without any quality guarantee.
This one-day workshop not only provides a platform to collect recent advances in all areas of online algorithms, but also highlight key challenges and open problems. The objective is to bring together scholars from different communities including but not limited to online algorithms, machine learning, mathematical optimization, streaming algorithms and complexity theory, to promote more interactions and collaborations between the communities.
Workshop Organizers
Thomas Erlebach (Durham University, UK)
Kazuo Iwama (Kyoto University, Japan)
Chung-Shou Liao (National Tsing Hua University, Taiwan)
Nicole Megow (University of Bremen, Germany)
Workshop Content & Format
The workshop consists of the following 6 invited talks, an open problem session and contributed talks from researchers who submit the abstract of their work to this workshop. There are three regular sessions (one in the morning and two in the afternoon) and a one-hour open problem session right before noon, where each regular session includes two 30-min invited talks and two 20-min contributed talks. The tentative schedule is shown below. There are no plans for publication of proceedings.
Invited Speakers
Yossi Azar (Tel-Aviv University, Israel)
Marcin Bienkowski (University of Wroclaw, Poland)
Christian Coester (University of Oxford, UK)
Christoph Dürr (CNRS, France)
Franziska Eberle (LSE, UK)
Benjamin Moseley (CMU, USA)
Important Dates
Submissions deadline: May 12, 5pm CET
Notification: May 15
Early registration deadline ICALP/Workshops: May 15
Speaker registration deadline: June 9
Workshop: July 10, 2023