WAOA 2026

News: The submission deadline was extended to July 2nd 2026.

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.
WAOA 2026 is co-located with ALGO 2026, which also hosts ALGOCLOUD, ALGOWIN, ATMOS, ESA, IPEC and WABI. ALGO 2026 will be held at the University of L’Aquila in L’Aquila, Italy.

Invited Speaker

Speaker: Standa Živný, University of Oxford

Title: Relaxations of Max-Cut and Beyond

Abstract: Given a graph whose maximum cut is of size \rho, can one find efficiently a cut of size 0.9ρ? This is not possible under Khot’s Unique Games Conjecture. What if the task is merely to find a 3-way cut of size at least 0.9ρ? Or to find a triangle-free subgraph of size 0.9ρ? In this talk I’ll tell you about these two problems and other examples of approximations of maximum homomorphism problems. Joint work with Tamio-Vesa Nakajima.

Accepted Papers

  • Fateme Abbasi, Martin Böhm, Jarosław Byrka, Matin Mohammadi and Yongho Shin: Servicing Matched Client Pairs with Facilities
  • Sven O. Krumke and Maren Manzke: The Target Date Scheduling Problem: Improved Upper and Lower Bounds
  • Leon Kullmann, Phuoc Lucky Trinh, Leon Kellerhals, Mitja Krebs, André Nichterlein and Stefan Schmid: Designing Caterpillars for Graphs: Approximation and Hardness
  • Tetiana Lavynska: Approximation Algorithms for Colorful Rainbow Domination: a Facility Location Problem on Graphs
  • Jarosław Byrka and Yongho Shin: Online Rounding Schemes for Edge Cover
  • Junho Hwang: A 5/4 bound for graphic s-t path TSP on subcubic graphs
  • Taha El Ghazi, Jonas Ellert, Chien-Chung Huang and Tatiana Starikovskaya: Streaming algorithms for computing coresets and k-median clustering in the Hamming space
  • Julian Born, Yann Disser, Maximilian Stahlberg and Linda Thelen: Cumulative Incremental Maximization of Decreasing Sequences
  • Benjamin Moseley, Kirk Pruhs, Marc Uetz and Rudy Zhou: Minimizing Completion Times of Stochastic Jobs on Parallel Machines is Hard
  • Shahin Kamali and Saba Yazdani: Geometric Burning Under L1 and L∞ Metrics, and Beyond
  • Jialin He, Nicholas Popescu and Chunjiang Zhu: Sublinear Edge Fault-Tolerant Hyperspanners for Hypergraphs
  • Susanne Albers and Wessel van der Heijden: Scheduling to Maximize Weighted Throughput with an Active-Time Budget
  • Sathish Govindarajan and Siddhartha Sarkar: Minimum-Membership Covering by Translates of a Convex Polygon
  • Siddhartha Sarkar: A PTAS for Axis-Parallel Separation of Points in Convex Position
  • Max Klimm, Marc Pfetsch, Martin Skutella and Lea Strubberg: Approximating the Network Design Problem for Potential-Based Flows
  • Simon Bartlmae, Paul Jünger and Elmar Langetepe: NP-Hardness and a PTAS for the Euclidean Steiner Line Problem

Important Dates

  • Paper submission deadline: June 28, 2026, 23:59 AoE July 2, 2026, 23:59 AoE
  • Notification: August 4, 2026
  • Camera-ready version: 30 August 2026
  • Conference: 3-4 September 2026

Program Committee

  • Antonios Antoniadis, University of Twente
  • Hans-Joachim Böckenhauer, ETH Zurich
  • Sami Davies, UC Berkeley
  • Max Deppert, Kiel University
  • Leah Epstein, University of Haifa
  • Yuri Faenza, Columbia University
  • Kim-Manuel Klein, Universität zu Lübeck (co-chair)
  • Alexander Lindermayr, Technische Universität Berlin
  • Monaldo Mastrolilli, SUPSI-IDSIA (co-chair)
  • Alantha Newman, École normale supérieure de Lyon
  • Kevin Schewior, University of Cologne
  • Hadas Shachnai, Technion
  • Hanna Sumita, Institute of Science Tokyo
  • Marc Uetz, University of Twente
  • Rob van Stee, University Siegen
  • Laura Vargas Koch, RWTH Aachen
  • Victor Verdugo, Pontificia Universidad Católica de Chile
  • Tjark Vredeveld, Maastricht University
  • Prudence Wong, University of Liverpool

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

Papers should be submitted via the EasyChair submission system.

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 will not be included in the published 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 2026, 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 2026 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

  • 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 
  • Roberto Solis-Oba, University of Western Ontario, CA