WAOA 2022

Scope

Approximation and online algorithms are fundamental tools to deal with computationally hard problems and problems in which the input is gradually disclosed over time. Both kinds of problems arise from a large number of applications in a variety of fields. The workshop focuses on the design and analysis of approximation and online algorithms. It also covers experimental methods used to design and analyze efficient approximation and online algorithms. It is colocated with ALGO 2022, which also hosts ESA, ALGOCLOUD, ALGOSENSORS and ATMOS. ALGO 2022 will take place September 5-9, 2022 in Potsdam, Germany.

Important Dates

  • Paper Submission (extended): June 27, 2022 July 1, 2022 (AOE)
  • Notification of acceptance: July 31, 2022
  • Camera ready: August 7, 2022
  • Conference dates: September 8-9, 2022, in Potsdam, Germany

Call for Papers

Authors are invited to submit an extended abstract or full paper of at most 11 pages excluding the title page, references, and an optional appendix. The submission should be typeset using a 10-point or larger font in a single-column format with ample spacing throughout and 2cm margins all around on A4-size paper. Proofs omitted due to space constraints must be placed in an appendix. This appendix can even comprise an entire full version of the paper. The appendix will be read by the program committee members at their discretion. In particular, appendices of accepted papers are not going to be published in the proceedings. The main part of the submission should therefore contain a clear technical presentation of the merits of the paper, including a discussion of the paper’s importance within the context of prior work and a description of the key technical and conceptual ideas used to achieve its main claims.

The conference employs a lightweight double-blind reviewing process. Submissions should not reveal the identity of the authors in any way. In particular, authors’ names, affiliations, and email addresses should not appear at the beginning or in the body of the submission. Authors should ensure that any references to their own related work is in the third person (e.g., not “We build on our previous work …” but rather “We build on the work of …”). Nothing should be done in the name of anonymity that weakens the submission or makes the job of reviewing the paper more difficult. In particular, references should not be omitted or anonymized.

Papers should be submitted electronically via the EasyChair submission system.

By submitting a paper the authors acknowledge that in case of acceptance at least one of the authors must register at ALGO 2022 and present the paper. The program committee may award a Best Paper Award to one of the accepted papers.

Topics

Papers are solicited in all research areas related to approximation and online algorithms, including, but not limited to:

  • Graph algorithms
  • Inapproximability results
  • Network design
  • Packing and covering
  • Paradigms for the design and analysis of approximation and online algorithms
  • Parameterized complexity
  • Scheduling problems
  • Algorithmic game theory
  • Algorithmic trading
  • Coloring and partitioning
  • Competitive analysis
  • Computational advertising
  • Computational finance
  • Cuts and connectivity
  • Geometric problems
  • Mechanism design
  • Resource augmentation
  • Real-world applications

Committees

Chairs

  • Parinya Chalermsook, Aalto University, Finland
  • Bundit Laekhanukit, Shanghai University of Finance and Economics, China

Steering Committee

  • Evripidis Bampis, Sorbonne Université, Paris, France
  • Thomas Erlebach, Durham University, UK
  • Christos Kaklamanis, University of Patras, Greece
  • Nicole Megow, Universität Bremen, Germany
  • Laura Sanita, Eindhoven University of Technology, The Netherlands
  • Martin Skutella, Technische Universität Berlin, Germany
  • Roberto Solis-Oba, University of Western Ontario, USA
  • Klaus Jansen, Christian-Albrechts-Universität zu Kiel, Germany

Program Committee

  • Hyung-Chan An (Yonsei University)
  • Amey Bhangale (University of California, Riverside)
  • Umang Bhaskar (Tata Institute of Fundamental Research)
  • Parinya Chalermsook (Aalto University)
  • Karthekeyan Chandrasekaran (University of Illinois Urbana-Champaign)
  • Karthik CS (Rutgers University)
  • Syamantak Das (Indraprastha Institute of Information Technology)
  • Franziska Eberle (London School of Economics and Political Science)
  • Jittat Fakcharoenphol (Kasetsart University)
  • Zachary Friggstad (University of Alberta)
  • Takuro Fukunaga (Chuo University)
  • Waldo Gálvez (Universidad de O’Higgins)
  • Chien-Chung Huang (École Normale Supérieure)
  • Łukasz Jeż (University of Wrocław)
  • Bundit Laekhanukit (Shanghai University of Finance and Economics)
  • Pasin Manurangsi (Google Research)
  • Eunjin Oh (Pohang University of Science and Technology)
  • Hanna Sumita (Tokyo Institute of Technology)
  • Zhihao Tang (Shanghai University of Finance and Economics)
  • Seeun William Umboh (The University of Sydney)
  • Yuhao Zhang (Shanghai Jiaotong University)

Invited Speaker

Tobias Mömke is Professor for Theoretical Computer Science at the University of Augsburg, Germany. He received his Doctor of Sciences degree at ETH Zurich in 2010. After his PhD, he was a postdoctoral researcher at KTH, Stockholm and at Saarland University, Germany. In 2017/18, he held a position as interim professor at University of Bremen, Germany. His research aims to develop new algorithmic approaches for hard optimization problems. A main focus of his work is the development of approximation algorithms for graph and scheduling problems. He received the FOCS best paper award in 2011 and a DFG Heisenberg Grant in 2020.

Proceedings

Proceedings will be published in the Springer series Lecture Notes in Computer Science after the workshop takes place. Selected papers presented at WAOA 2022 will be invited to a special issue of Theory of Computing Systems.

Accepted Papers

Hsiang-Hsuan Liu and Jonathan Toole-Charignon. The Power of Amortized Recourse for Online Graph Problems

Ilan Cohen. Stochastic graph exploration with limited resources

Evripidis Bampis, Bruno Escoffier and Michalis Xefteris. Canadian Traveller Problem with Predictions

Matej Lieskovský and Jiří Sgall. Graph burning and non-uniform $k$-centers for small treewidth

Devin Smedira and David Shmoys. Scheduling Appointments Online: The Power of Deferred Decision-Making

Lisa Hellerstein, Devorah Kletenik, Naifeng Liu and R. Teal Witter. Adaptivity Gaps for the Stochastic Boolean Function Evaluation Problem

Moritz Buchem, Linda Kleist and Daniel Schmidt Genannt Waldschmidt. Scheduling with Machine Conflicts

Andreas Abels, Leon Ladewig, Kevin Schewior and Moritz Stinzendörfer. Knapsack Secretary Through Boosting

Júlia Baligács, Yann Disser, Nils Mosis and David Weckbecker. An Improved Algorithm for Open Online Dial-a-Ride

Rajni Dabas, Naveen Garg, Neelima Gupta and Dilpreet Kaur. Locating Service and Charging stations

Maike Buchin, Anne Driemel, Ioannis Psarros, Dennis Rohde and Koen van Greevenbroek. Approximating Length-Restricted Means under Dynamic Time Warping

Fabian Klute, Sujoy Bhore and Jelle Oostveen. On Streaming Algorithms for Geometric Independent Set and Clique