European Symposia on Algorithms

ESA Test-of-Time Award 2018

The ESA Test-of-Time Award (ToTA) recognizes excellent papers in algorithms research that were published in the ESA proceedings 19-21 years ago and which are still influential and stimulating for the field today. For the 2018 award, papers from ESA'97 to ESA'99 were considered. Because WAE merged in with ESA, the Steering Committee decided that the papers from WAE'97 to WAE'99 were also to be considered.

The award committee selected the following paper for the ESA ToTA 2018. The paper stands out as a classic in efficient data structure design and provides what is still an essential building block in the fastest-possible deterministic comparison-based minimum spanning tree algorithm.

Bernard Chazelle
Car-Pooling as a Data Structuring Device: The Soft Heap
Proceedings ESA'98, pp. 35-42, also in: Journal of the ACM 47(6): 1012-1027 (2000)

The paper presents an ingenious data structure, the soft heap, which realizes an intricate compromise between what is possible (speed) and what is useful (accuracy). The soft heap is an approximate priority queue, in the sense that the items it returns are not necessarily items of minimum key. A soft heap is allowed to increase the keys of some, but not too many, of its items, to facilitate what Chazelle calls the "car-pooling equivalent of data structures". All soft heap operations take constant amortized time, given a desired level of accuracy. Soft heaps were devised by Chazelle to obtain a deterministic, comparison-based O(mα(m,n))-time algorithm for the fundamental minimum spanning tree problem. Twenty years on, this is still the fastest algorithm of its kind. Soft heaps were also used by Pettie and Ramachandran (2002) to obtain an optimal algorithm for the problem, i.e., with algorithmic complexity equal to its decision-tree complexity, albeit with an as yet unknown running time. The soft heaps paper has not aged over the years and continues to inspire as a fundamental achievement.

Award Committee: Giuseppe F. Italiano (Rome), Jan van Leeuwen (Utrecht), Uri Zwick (Tel Aviv)

ESA Test-of-Time Award 2017

The ESA Test-of-Time Award (ToTA) recognizes excellent papers in algorithms research that were published in the ESA proceedings 19-21 years ago and which are still influential and stimulating for the field today. For the 2017 award, papers from ESA'96 to ESA'98 were considered.

The award committee selected the following paper for the ESA ToTA 2017. The paper stands out as a classic in the algorithms field and continues to be cited as an exemplary study in its field.

James Abello, Adam L. Buchsbaum, and Jeffery R. Westbrook
A Functional Approach to External Graph Algorithms
Proceedings ESA'98, pp. 332-343, also in: Algorithmica 32 (2002) 437-458

The paper deals with the design of algorithms that operate on massive data sets in external memory. Building on the well-known I/O model of complexity by Aggarwal and Vitter, the authors introduce a novel design principle for external algorithms based purely on functional transformations of the data, which facilitates standard checkpointing and program optimization techniques. Illustrated on a variety of graph problems, their approach is proved to be elegant and versatile in the design of both deterministic and randomized external algorithms while the resulting I/O complexities remain competitive. Functional algorithms are also designed for semi-external problems, in which the nodes fit in main memory but the connecting edges are abundant and only available in external memory. The paper is an excellent illustration of how general principles of functional program design and model-based complexity can remain in harmony in the field of external algorithms.

Award Committee: Giuseppe F. Italiano (Rome), Mike Paterson (Warwick), Jan van Leeuwen (Utrecht)

ESA Test-of-Time Award 2016

The ESA Test-of-Time Award (ESA ToTA) recognizes excellent papers in algorithms research that were published in the ESA proceedings 19-21 years ago and which are still influential and stimulating for the field today. In this second year in which the award is given, papers from ESA'95 to ESA'97 were considered.

The award committee selected the following paper for the ESA ToTA 2016. The paper stands out as a classic in the algorithms field and by its excellent citation record still relevant today.

From ESA 95-97:

Boris V. Cherkassky, Andrew V. Goldberg:
Negative-cycle detection algorithms
Proceedings ESA'96, also in: Mathematical Programming 85:2 (1999) 277-311

The paper by Cherkassky and Goldberg deals with the problem of finding a negative-length cycle in a network or proving that there is none. Algorithms for this are a combination of a shortest-path algorithm and a negative-cycle detection strategy. The authors analyse known algorithms and some new ones and determine the best combinations. Novel instance generators are used in this study. The paper is a model experimental paper in algorithms.

Award Committee: Kurt Mehlhorn (Saarbrucken), Mike Paterson (Warwick), and Jan van Leeuwen (Utrecht)

ESA Test-of-Time Award 2015

The ESA Test-of-Time Award (ESA ToTA) recognizes outstanding papers in algorithms research that were published in the ESA proceedings 19-21 years ago and which are still influential and stimulating for the field today. Exceptionally, in this first year in which award is given, the ESA ToTA 2015 committee was asked to consider all qualifying papers from ESA 93-95 and ESA 94-96, respectively.

The award committee selected the following two papers for the ESA ToTA 2015. The papers stand out for their impact and wide use in the algorithms field, and for their excellent citation records up to the present day.

From ESA 93-95:

Mechthild Stoer, Frank Wagner:
A Simple Min Cut Algorithm
Proceedings ESA'94, also in: JACM 44:4 (1997) 585-591

The minimum cut problem in graphs is a basic problem in network analysis and is needed, for example, as the separation routine in branch-and-cut algorithms for the Traveling Salesman problem. Stoer and Wagner gave an elegant and efficient algorithm for the problem that avoids the computation of maximum flows, building upon previous work by Nagamochi and Ibaraki. The same algorithm was independently found by Frank. The algorithm continues to be taught because of its elegance and used because of its efficiency and ease of implementation.

From ESA 94-96:

Sudipto Guha, Samir Khuller:
Approximation Algorithms for Connected Dominating Sets
Proceedings ESA'96, also in: Algorithmica 20:4 (1998) 374-387

It is natural to require connectedness as an additional constraint for a dominating set, for example, in ad hoc wireless networks. Domination guarantees coverage and connectedness guarantees communication between the selected nodes. Guha and Khuller gave polynomial algorithms for a logarithmic-factor approximation to its solution. Under the usual assumptions, this is the best possible. Their much-cited work has stimulated similar research for connected variants of many other graph problems.

Award Committee: Jan van Leeuwen, Kurt Mehlhorn and Mike Paterson