European Symposia on Algorithms

General information

The Symposium covers research in efficient algorithms and data structures in computer science, discrete applied mathematics, operations research and mathematical programming. Starting from 2002, the symposium has two tracks:

  • Design and Analysis Track

    Design and mathematical analysis of algorithms
  • Engineering and Application Track

    Real-world applications, engineering and experimental analysis of algorithms

The creation of two tracks in ESA follows the incorporation of the annual Workshop on Algorithm Engineering (WAE) into ESA.

Each track has its own program committee. Papers are submitted to a particular track, but the committees have the right to move papers between tracks.

In 2014, the ESA community decided to start an ESA Test-of-Time Award to recognize paper(s) from ESA Proceedings from 19-21 years ago which are still influential and stimulating for the field today.

News

  • The ESA Test-of-Time Award 2018 goes to

    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.

    more information

ESA Locations and Links