Online algorithms need to make decisions based on information that is provided to them as the algorithms execute, without knowledge of the information that will be provided to them in the future. This uncertainty makes the design of online algorithms very challenging. Approximation algorithms face a different kind of challenges as they need to find the best solutions for problems that have very large solution spaces.

This special issue of Theory of Computing Systems is devoted to the publication of a selected set of papers that were presented at the 15th International Workshop on Approximation and Online Algorithms (WAOA 2017) which took place in Vienna, Austria, September 7-8 of 2017. Each one of the 23 papers accepted for presentation at the workshop was reviewed by at least 3 members of the program committee. The program committee invited the authors of the four best papers presented at the workshop to write full versions of their papers and to submit them to the special issue. Each one of these papers was thoroughly reviewed by two experts, in accordance with the high standards of this journal.

In “Lower bounds for several online variants of bin packing”, the problem of packing a set of items of different sizes into unit size bins is studied. The bin packing problem is a fundamental problem in optimization that has been extensively studied, partly due to its large number of applications . The authors show how to use a technique based on the use of adaptive constructions to compute new lower bounds for several variants of the online bin packing problem.

The paper “On conceptually simple algorithms for variants of online bipartite matching” studies another fundamental optimization problem: Computing a maximum matching in a bipartite graph. The maximum bipartite matching problem has been widely studied in the literature and many algorithms for it exist. This paper is interesting because most of existing algorithms for this problem are complex and hard to understand and implement. The authors of this paper focus on the study of simple algorithms for the problem.

“Online search in two-dimensional environment” studies a classical graph search problem: Given a graph the goal is to find a given mobile entity that initially resides in one of the nodes of the graph by deploying the smallest possible number of searching agents that look for the entity by moving through the edges of the graph. The authors study the problem assuming that the graph is a subgraph of the two-dimensional grid and neither the mobile entity nor the searching agents have full knowledge of the graph.

The last paper, “Efficient dynamic approximate distance oracles for vertex-labeled planar graphs” considers a graph where each vertex has a label and given a starting vertex u and a desired label ℓ the goal is to find the closest vertex to u with label ℓ. The paper describes three different efficient algorithms for approximately solving this problem. For a given vertex u and label ℓ the algorithms are only guaranteed to find a vertex with label ℓ that is at most at a distance 1 + 𝜖 times the distance from u to the closest vertex with label ℓ, where 𝜖 ≥ 0. The smaller the value of 𝜖 is the larger the running times of the algorithms are.

We would like to thank all the authors who contributed to this special issue and we also want to thank the reviewers, who carefully read the papers and made many valuable suggestions. Finally, we thank Springer and the staff of Theory of Computing Systems for their help in publishing this issue.

Roberto Solis-Oba and Rudolf Fleischer, August 2019.