ALGO2024

WAOA 2024

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 on Approximation and Online Algorithms (WAOA) 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.

WAOA 2024 is co-located with ALGO 2024, which also hosts ESA, ALGOCLOUD, ALGOWIN, ATMOS, IPEC, and WABI. ALGO 2024 will take place at Royal Holloway, University of London in Egham, United Kingdom.

Important Dates

  • Paper submission deadline: 3 July 2024, 23:59 AoE (EasyChair submission system)
  • Notification: 31 July 2024
  • Camera-ready version: 9 August 2024
  • Conference: 5-6 September 2024

Invited Speaker

  • Speaker: Rico Zenklusen, ETH Zürich
  • Title: Advances in Approximation Algorithms for Tree and Connectivity Augmentation
  • Abstract: Augmentation problems are a fundamental class of Network Design problems. The goal is to find a cheapest way to increase a graph’s (edge-)connectivity by adding edges from a given set of options. The Minimum Spanning Tree Problem is one of its most elementary examples, which can be interpreted as determining a cheapest way to increase the edge-connectivity of a graph from 0 to 1. The next step, to increase from 1 to 2, leads to the heavily studied Tree Augmentation Problem, and the more general problem of increasing the edge-connectivity by 1 of an arbitrary graph is known as Connectivity Augmentation. While these problems admit simple 2-approximations, obtaining approximation factors below 2 has proven challenging. This talk has several goals, namely:
    • Providing a brief introduction to Tree and Connectivity Augmentation.
    • Discussing relevant algorithmic techniques that have recently led to better-than-2 approximations for these problems, including the Relative Greedy method and an interesting connection of it to local search procedures.
    • Demonstrating how these techniques can be leveraged to obtain better-than-2 approximations for (weighted) augmentation problems.

Accepted Papers

  • Sander Aarts, Jacob Dentes, Manxi Wu and David B. Shmoys. Bounding the price-of-fair-sharing using knapsack-cover constraints to guide near-optimal cost-recovery algorithms
  • Aflatoun Amouzandeh and Rob van Stee. Improved online scheduling with restarts on a single machine
  • Sergio Cabello and Panos Giannopoulos. Searching in Euclidean Spaces with Predictions
  • Rajesh Chitnis, Samuel Thomas and Anthony Wirth. Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths
  • Tim A. Hartmann and Tom Janßen. Approximating delta-Covering
  • Stefan Hougardy and Karolina Tammemaa. Fast Approximation Algorithms for Euclidean Minimum Weight Perfect Matching
  • Svein Høgemo. Tight Approximation Bounds on a Simple Algorithm for Minimum Average Search Time in Trees
  • Dylan Hyatt-Denesik, Danny Blom, Afrouz Jabal Ameli and Bart Smeulders. Approximation Algorithms for k-Scenario Matching
  • Tung-Wei Kuo. Online Deterministic Minimum Cost Bipartite Matching with Delays on a Line
  • Kefu Lu and Mason Marchetti. Maximizing Throughput for Parallel Jobs with Speed-up Curves
  • Zeev Nutov. Improved approximation algorithms for covering pliable set families and flexible graph connectivity
  • Richard Shapley and David Shmoys. Small additive error for unsplittable multicommodity flow in outerplanar graphs
  • Rene Sitters, Tim Oosterwijk and Steven Miltenburg. Complexity of Fixed Order Routing
  • Mihail Stoian. Approximate Min-Sum Subset Convolution
  • Philip Whittington. Online String Attractors

Program Committee

  • Spyros Angelopoulos, CNRS and Sorbonne University, FR
  • Antonios Antoniadis, University of Twente, NL
  • Sujoy Bhore, IIT Bombay, IN
  • Marcin Bieńkowski, University of Wrocław, PL (co-chair)
  • Hans-Joachim Böckenhauer, ETH Zürich, CH
  • Maike Buchin, Ruhr University Bochum, DE
  • Panagiotis Charalampopoulos, Birkbeck, University of London, UK
  • Marek Chrobak, University of California, Riverside, US
  • Christian Coester, University of Oxford, UK
  • Matthias Englert, University of Warwick, UK (co-chair)
  • Naveen Garg, IIT Delhi, IN
  • Meng He, Dalhousie University, CA
  • Martin Hoefer, Goethe Universität, DE
  • Jochen Koenemann, University of Waterloo, CA
  • Shi Li, Nanjing University, CN
  • Alantha Newman, Université Grenoble Alpes, FR
  • Zeev Nutov, The Open University of Israel, IL
  • Kevin Schewior, University of Southern Denmark, DK
  • Chris Schwiegelshohn, Aarhus University, DK
  • Hadas Shachnai, Technion, IL
  • Joachim Spoerhase, University of Sheffield, UK
  • David Wajc, Technion, IL
  • Prudence Wong, University of Liverpool, UK
  • Meirav Zehavi, Ben-Gurion University, IL

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, IL
  • Martin Skutella, Technische Universität Berlin, DE
  • Roberto Solis-Oba, University of Western Ontario, CA

Call for Papers

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

  • Algorithmic game theory
  • Algorithmic trading
  • Coloring and partitioning
  • Competitive analysis
  • Computational advertising
  • Computational finance
  • Cuts and connectivity
  • FPT-approximation algorithms
  • Geometric problems
  • Graph algorithms
  • Inapproximability results
  • Mechanism design
  • Network design
  • Packing and covering
  • Paradigms for the design and analysis of approximation and online algorithms
  • Resource augmentation
  • 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 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.

Results previously published (or scheduled for publication) in another conference proceedings or journal will not be accepted at WAOA. 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 2024, 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., not “We build on our previous work …” but rather “We build on the work of …”). The purpose of the double-blind reviewing is to help PC members and external reviewers come to an initial judgement 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 makes the job of reviewing the paper more difficult. In particular, important references should not be omitted or anonymized. In addition, authors should feel free to disseminate their ideas or draft versions of their paper as they normally would. For example, authors may post drafts of their papers on the web, submit them to arXiv, and give talks on their research ideas.

COI with PC members

When submitting a paper, authors will be asked to indicate Conflict of Interest (CoI) with PC members. A CoI is limited to the following categories:

  • 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.
  • Person with the same affiliation.
  • Involved in an alleged incident of harassment. (It is not required that the incident be reported.)
  • PC member owes author a favor (e.g., recently requested a reference letter).
  • Frequent or recent collaborator (within 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 2024 proceedings will be published by Springer in the Lecture Notes in Computer Science (LNCS). Selected papers presented at WAOA 2024 will be invited to a special issue of Theory of Computing Systems.