ALGO2025

WAOA

2025

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 types of problems arise from a myriad of applications in various fields. The Workshop on Approximation and Online Algorithms (WAOA) focuses on the design and analysis of approximation and online algorithms. It is co-located with ALGO 2025, which also hosts ESA, ALGOCLOUD, ALGOWIN, ATMOS and IPEC. ALGO 2025 will take place in the beautiful city of Warsaw in Poland.

Important dates

  • Paper submission deadline: July 6, 2025, 23:59 AoE
    (EasyChair submission page)
  • Notification: August 7, 2025
  • Camera-ready version: August 12, 2025 August 14, 2025
  • Conference dates: September 18-19, 2025

Invited speaker

Speaker: Sahil Singla, Georgia Tech

Title:  Beyond Competitive Analysis for Online Algorithms

Abstract:

Competitive analysis has long been the standard framework for evaluating online algorithms under worst-case inputs. While powerful, it often yields weak or even vacuous bounds for central problems—such as online matchings, load balancing, and network design. Yet many of these problems become far more tractable once we move beyond the purely worst-case lens. This has motivated a range of beyond worst-case models that exploit additional structure or information to achieve stronger guarantees.

In this talk, I will survey several such models and their algorithmic implications: stochastic arrival processes and prophet-type inequalities; algorithms with sample access to the input; recourse models that allow limited revisions to past decisions; and optimal policy design as a benchmark beyond the offline optimum. I will emphasize unifying ideas across these approaches and highlight recent advances that overcome long-standing worst-case barriers.

Accepted papers

  • Bob Krekelberg and Alison Hsiang-Hsuan Liu. On the FirstFit Algorithm for Online Unit-Interval Coloring
  • Yann Disser, Max Klimm, Annette Lutz and Lea Strubberg. Incremental–Decremental Maximization
  • Hiroshi Fujiwara, Rina Atsumi and Hiroaki Yamamoto. Max-Min and 1-Bounded Space Algorithms for the Bin Packing Problem
  • Fritz Bökler, Markus Chimani and Henning Jasper. Simple Approximations for General Spanner Problems
  • David Fischer, Hauke Brinkop and Klaus Jansen. Robust Scheduling on Uniform Machines
  • Martijn van Ee and Rene Sitters. Approximation algorithms for graph search with imperfect detection
  • D Ellis Hershkowitz and Niklas Dahlmeier. Low Recourse Arborescence Forests Under Uniformly Random Arcs
  • Shamisa Nematollahi and Daniel Vaz. Buy-at-Bulk Facility Location on Trees
  • Andreas Abels, Mariia Anapolska and Christina Büsing. Interval-Constrained Bipartite Matching over Time
  • Qiming Cui and Michael Dinitz. Controlling Tail Risk in Two-Slope Ski Rental
  • Yan Couto and Cristina Fernandes. Hardness of Dynamic Core and Truss Decompositions
  • Kanstantsin Pashkovich and Thomas Snow. Online Algorithm for Fractional Matchings with Edge Arrivals in Graphs of Maximum Degree Three
  • Jubayer Nirjhor and Nicole Wein. Improved Online Sorting
  • Elisabet Burjons and Matthias Gehnen. Online General Knapsack with Reservation Costs
  • Riju Bindua, Minati De, Naveen Garg and Kanav Singla. The Online Piercing Set Problem With Recourse

Program committee 

  • Umang Bhaskar, Tata Institute of Fundamental Research
  • Karthekeyan Chandrasekaran, University of Illinois Urbana-Champaign
  • Yann Disser, TU Darmstadt
  • Franziska Eberle, TU Berlin
  • Yuri Faenza, Columbia University
  • Cristina Fernandes, Universidade de São Paulo
  • Thekla Hamm, TU Eindhoven
  • Lisa Hellerstein, New York University
  • Sungjin Im, University of California, Santa Cruz
  • Naonori Kakimura, Keio University
  • Kim-Manuel Klein, Universität zu Lübeck
  • Jannik Matuschke, KU Leuven (co-chair)
  • Arturo Merino, Universidad de O’Higgins
  • Malin Rau, Chalmers University of Technology
  • Rebecca Reiffenhäuser, Universiteit van Amsterdam
  • Melanie Schmidt, Heinrich-Heine-Universität Düsseldorf
  • Seeun William Umboh, The University of Melbourne
  • José Verschae, Pontificia Universidad Católica de Chile (co-chair)
  • Yu Yokoi, Institute of Science Tokyo

Call for papers

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

  • Algorithmic game theory
  • Coloring and partitioning
  • Computational economics and mechanism design
  • Experimental methods for approximation and online algorithms
  • FPT-approximation algorithms
  • Geometric problems
  • Graph algorithms and network design
  • Inapproximability results
  • Packing and covering
  • Matroids and submodular functions
  • New paradigms in approximation and online optimization
  • Online selection problems
  • Resource augmentation
  • Relaxations and tightness of formulations
  • Robust and stochastic problems
  • Scheduling problems

Submission guidelines

Authors are invited to submit an extended abstract or full paper of at most 10 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 and 2cm margins all around on A4-size paper. The appendix must contain all omitted proofs or, alternatively, a full version of the paper. The appendix will be read by the program committee at their discretion but is not going to be published in the proceedings. The central 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.

Results previously published (or scheduled for publication) in another conference proceedings or journal will not be accepted. Simultaneous submission to journals or other conferences with published proceedings is not permitted. By submitting a paper, the authors acknowledge that in case of acceptance, at least one of the authors must register at ALGO 2025, attend the conference onsite and present the paper. The program committee may award a Best Paper Award to one of the accepted papers.

Double-blind reviewing 

The conference will employ 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., “We build on the work of …” instead of “We build on our previous work …”). The purpose of the double-blind reviewing is to help PC members and external reviewers come to an initial judgment about the paper without bias, not to make it impossible for them to discover the authors if they were to try. Nothing should be done in the name of anonymity that weakens the submission or hinders the reviewing process. In particular, important references should not be omitted or anonymized. Authors should feel free to disseminate their ideas (e.g., via talks) or draft versions of their paper (e.g., on arXiv or other repositories).

COI with PC members 

At submission, authors will be asked to indicate a Conflict of Interest (COI) with members of the program committee. A COI is limited to the following categories: 

  • A family member or close friend. 
  • Ph.D. advisor or advisee (no time limit), or postdoc or undergraduate mentor or mentee within the past 5 years. 
  • A person with the same affiliation. 
  • A person involved in an alleged incident of harassment. (It is not required that the incident is reported.) 
  • A PC member who owes the author a favor (e.g., who recently requested a reference letter).
  • A frequent or recent collaborator (within the last 5 years) who you believe cannot objectively review your work.

PC submissions 

Submissions authored or co-authored by members of the program committee are allowed but will be subject to a stricter review process. 

Paper submission and proceedings 

Papers should be submitted electronically via the EasyChair submission system. The WAOA 2025 proceedings will be published by Springer in the Lecture Notes in Computer Science (LNCS) series. A subset of the accepted articles might be invited for a special issue of Acta Informatica.

Steering committee 

  • Roberto Solis-Oba, University of Western Ontario, CA 
  • Evripidis Bampis, Sorbonne Université, FR 
  • Thomas Erlebach, Durham University, UK 
  • Christos Kaklamanis, University of Patras, GR 
  • Nicole Megow, Universität Bremen, DE 
  • Laura Sanità, Bocconi University, IT
  • Martin Skutella, Technische Universität Berlin, DE