ESA 2022

Scope

The European Symposium on Algorithms (ESA) is one of the premier conferences on algorithms. It is organized in collaboration with the European Association for Theoretical Computer Science (EATCS) and is a part of ALGO 2022.

Important Dates

  • Paper submission deadline: April 21, 23:59 AoE. (EasyChair submission system)
  • Notification: June 18
  • Camera ready: July 3
  • LIPIcs receives files: July 8
  • Proceedings published: September 2
  • Conference: September 5-7, 2022, in Potsdam, Germany (early on Monday – late on Wednesday)

Call for Papers

The symposium seeks original algorithmic contributions for problems with relevant theoretical and/or practical applications. Papers with a strong emphasis on the theoretical analysis of algorithms should be submitted to Track A, while papers reporting on the results of extensive experimental evaluations and/or providing original contributions to the engineering of algorithms for practical applications should be submitted to Track B. Submissions that prove or explain known results in a much clearer, simpler or more elegant way than done before should be submitted to track S. There will be a Best Student Paper Award as well as a Best Paper Award, both sponsored by EATCS. In order for a paper to be considered for the Best Student Paper Award, all of its authors are required to be students.

Paper submission and proceedings

Papers should be submitted electronically via the EasyChair submission system. The ESA 2022 proceedings will be published in the Leibniz International Proceedings in Informatics (LIPIcs) series.

Submission Guidelines

Authors are invited to submit an extended abstract or full paper of at most 11 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. We recommend, but not strictly require, making your initial submission adhere to LIPIcs publication guidelines. 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. These guidelines are strict: submissions deviating significantly from these guidelines risk being rejected without consideration of their merits. Papers should be submitted electronically via the EasyChair submission system. Results previously published (or scheduled for publication) in another conference proceedings or journal will not be accepted at ESA. Simultaneous submission to other conferences with published proceedings, or to multiple tracks of ESA 2022, is also not permitted. By submitting a paper the authors acknowledge that in case of acceptance, at least one of the authors must register at ALGO 2022, attend the conference, and present the paper.

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 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 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. In case there exist publicly available versions of the submission online, the authors might mention this in their submission (without providing references/links), and briefly explain the differences if any. Alternatively, they might communicate the details to the chairs, who will keep them confidential unless revealing them to the PC is needed for a fair judgment. Authors with further questions on double-blind reviewing are encouraged to contact the PC chairs.

Topics

Papers presenting original research in all areas of algorithmic research are sought, including but not limited to:

  • Algorithm engineering
  • Algorithmic aspects of networks
  • Algorithmic game theory
  • Algorithmic Data Science
  • Approximation algorithms
  • Computational biology
  • Computational finance
  • Computational geometry
  • Combinatorial optimization
  • Data compression
  • Data structures
  • Databases and information retrieval
  • Distributed and parallel computing
  • Graph algorithms
  • Hierarchical memories
  • Heuristics and meta-heuristics
  • Mathematical programming
  • Mobile computing
  • Online algorithms
  • Parameterized algorithms
  • Pattern matching
  • Quantum computing
  • Randomized algorithms
  • Scheduling and resource allocation problems
  • Streaming algorithms

Announcement: ESA Track S

This year, the European Symposium on Algorithms ESA’22 will have a Track S  (for Simplicity) inviting contributions that simplify algorithmic results.

We would like to expand the community around simplification of algorithmic
results, encourage and reward research towards simplification and clarity. 
We find that simpler algorithms are easier to implement, bridging the gap
between theory and practice, and we find that new simple or elegant proofs
are easier to understand and to teach, and may contain interesting new
insights whose relevance only the future will reveal.

Scope: We invite submissions that prove or explain known results in a
much clearer, simpler or more elegant way than done before. Submissions
that improve on the state of the art from a theoretical or practical
viewpoint should instead be submitted to tracks A or B.

Paper assessment: Contingent on being in scope for ESA, submitted
papers will primarily be judged on the simplicity and elegance of their
proofs or algorithms, and the clarity of their presentation.

Track S will run as an experiment for the 2022 ESA in Potsdam, Germany. 
It will have its own PC and PC chair, and the submission/acceptance
deadlines follow the schedule for tracks A and B.

Accepted Papers

  • Valentin Bartier, Nicolas Bousquet and Amer Mouawad. Galactic Token Sliding
  • Bernhard Haeupler, D. Ellis Hershkowitz and Goran Zuzic. Adaptive-Adversary-Robust Algorithms via Small Copy Tree Embeddings
  • Marek Szykuła and Adam Zyzik. An Improved Algorithm for Finding the Shortest Synchronizing Words
  • Sheng Yang, Samir Khuller, Sunav Choudhary, Kanak Mahadik and Subrata Mitra. Correlated Stochastic Knapsack with a Submodular Objective
  • Amit Chakrabarti and Themistoklis Haris. Counting Simplices in Hypergraph Streams
  • Nikhil Bansal and Christian Coester. Online metric allocation and time-varying regularization
  • Jonas Ellert. Lyndon Arrays Simplified
  • Aleksander Figiel, Vincent Froese, André Nichterlein and Rolf Niedermeier. There and Back Again: On Applying Data Reduction Rules by Undoing Others
  • Tim Zeitz and Nils Werner. Combining Predicted and Live Traffic with Time-Dependent A* Potentials
  • Andrew Goldberg, Yuanyuan Dong, Alexander Noe, Nikos Parotsidis, Mauricio Resende and Quico Spaen. A Local Search Algorithm for Large Maximum Weight Independent Set Problems
  • Susanne Albers and Sebastian Schubert. Tight Bounds for Online Matching in Bounded-Degree Graphs with Vertex Capacities
  • Thomas Erlebach, Murilo de Lima, Nicole Megow and Jens Schlöter. Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty
  • Aleksander Łukasiewicz and Przemysław Uznański. Cardinality estimation using Gumbel distribution
  • Alejandro Flores-Velazco. Improved Search of Relevant Points for Nearest-Neighbor Classification
  • Chien-Chung Huang and François Sellier. Maximum Weight b-Matchings in Random-Order Streams
  • Fedor Fomin, Petr Golovach, Danil Sagunov and Kirill Simonov. Longest Cycle above Erdős–Gallai Bound
  • Antonios Antoniadis, Mark de Berg, Sándor Kisfaludi-Bak and Antonis Skarlatos. Computing Smallest Convex Intersecting Polygons
  • Rajmohan Rajaraman and Omer Wasim. Improved bounds for online balanced graph re-partitioning
  • Esther Ezra and Micha Sharir. Intersection Searching amid Tetrahedra in 4-space and Efficient Continuous Collision Detection
  • Jendrik Brachter and Pascal Schweitzer. A Systematic Study of Isomorphism Invariants of Finite Groups via the Weisfeiler-Leman Dimension
  • Łukasz Bożyk and Michał Pilipczuk. Polynomial kernel for immersion hitting in tournaments
  • Bartłomiej Bosek and Anna Zych-Pawlewicz. Dynamic Coloring of Unit Interval Graphs with Limited Recourse Budget
  • Baris Can Esmer, Ariel Kulik, Dániel Marx, Daniel Neuen and Roohani Sharma. Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
  • Evangelos Kosinas, Loukas Georgiadis, Giuseppe F. Italiano and Thodoris Dimas. Computing the $4$-Edge-Connected Components of a Graph: An Experimental Study
  • Hans L. Bodlaender, Carla Groenland and Hugo Jacob. List Colouring Trees in Logarithmic Space
  • Travis Gagie. Simple worst-case optimal adaptive prefix-free coding
  • Faisal Abu-Khzam, Henning Fernau, Benjamin Gras, Mathieu Liedloff and Kevin Mann. Enumerating Minimal Connected Dominating Sets
  • D Ellis Hershkowitz and Jason Li. O(1) Steiner Point Removal in Series-Parallel Graphs
  • Jonathan Allcock, Yassine Hamoudi, Antoine Joux, Felix Klingelhoefer and Miklos Santha. Classical and quantum algorithms for variants of Subset-Sum via dynamic programming
  • Han Jiang, Shang-En Huang, Thatchaphol Saranurak and Tian Zhang. Vertex Sparsifiers for Hyperedge Connectivity
  • Panagiotis Charalampopoulos, Tomasz Kociumaka, Jakub Radoszewski, Solon Pissis, Wojciech Rytter, Tomasz Walen and Wiktor Zuba. Approximate Circular Pattern Matching
  • Jiehua Chen and Sanjukta Roy. Multi-Dimensional Stable Roommates in 2-Dimensional Euclidean Space
  • Oswin Aichholzer, Erik Demaine, Matias Korman, Anna Lubiw, Jayson Lynch, Zuzana Masarova, Mikhail Rudoy, Virginia Vassilevska Williams and Nicole Wein. Hardness of Token Swapping on Trees
  • Monika Henzinger, Ami Paz and A. R. Sricharan. Fine-Grained Complexity Lower Bounds for Families of Dynamic Graphs
  • Younan Gao and Meng He. Faster Path Queries in Colored Trees via Sparse Matrix Multiplication and Min-Plus Product
  • Debajyoti Kar, Arindam Khan and Andreas Wiese. Approximation Algorithms for ROUND-UFP and ROUND-SAP
  • Manoj Gupta and Dipan Dey. Near Optimal Algorithm for Fault Tolerant Distance Oracle and Single Source Replacement Path problem
  • Zachary Friggstad and Mahya Jamshidian. Improved Polynomial-Time Approximations for Clustering with Minimum Sum of Radii or Diameters
  • Sourav Chakraborty, Kuldeep S. Meel and N.V. Vinodchandran. Distinct Elements in Streams: An Algorithm for the (Text) Book
  • Syamantak Das and Andreas Wiese. A simpler QPTAS for scheduling jobs with precedence constraints
  • Kobi Bodek and Moran Feldman. Maximizing Sums of Non-monotone Submodular and Linear Functions: Understanding the Unconstrained Case
  • Dušan Knop and Martin Koutecky. Scheduling Kernels via Configuration LP
  • Martin Balko, Steven Chaplick, Siddharth Gupta, Robert Ganian, Michael Hoffmann, Pavel Valtr and Alexander Wolff. Bounding and Computing Obstacle Numbers of Graphs
  • Argyrios Deligkas, Michail Fasoulakis and Evangelos Markakis. A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games
  • Eduard Eiben, Robert Ganian, Iyad Kanj, Sebastian Ordyniak and Stefan Szeider. Finding a Cluster in Incomplete Data
  • Alexander Dobler, Manuel Sorge and Anaïs Villedieu. Turbocharging Heuristics for Weak Coloring Numbers
  • Georg Anegg, Laura Vargas Koch and Rico Zenklusen. Techniques for Generalized Colorful k-Center Problems
  • Thomas Bläsius and Philipp Fischbeck. On the External Validity of Average-Case Analyses of Graph Algorithms
  • Manuel Cáceres, Massimo Cairo, Andreas Grigorjew, Shahbaz Khan, Brendan Mumey, Romeo Rizzi, Alexandru Tomescu and Lucia Williams. Width Helps and Hinders Splitting Flows
  • Benjamin Merlin Bumpus, Bart M. P. Jansen and Jari J. H. de Kroon. Search-Space Reduction via Essential Vertices
  • Stefan Walzer. Insertion Time of Random Walk Cuckoo Hashing below the Peeling Threshold (extended abstract)
  • Miriam Goetze, Paul Jungeblut and Torsten Ueckerdt. Efficient Recognition of Subgraphs of Planar Cubic Bridgeless Graphs
  • Sujoy Bhore, Arnold Filtser, Hadi Khodabandeh and Csaba Toth. Online Spanners in Metric Spaces
  • Florian Barth, Stefan Funke and Claudius Proissl. An Upper Bound on the Number of Extreme Shortest Paths in Arbitrary Dimensions
  • Alexander Tiskin. Fast RSK correspondence by doubling search
  • Anna Arutyunova and Heiko Röglin. The Price of Hierarchical Clustering
  • Arghya Bhattacharya, Helen Xu, Abiyaz Chowdhury, Rezaul A. Chowdhury, Rathish Das, Rob Johnson, Rishab Nithyanand and Michael A. Bender. When Are Cache-Oblivious Algorithms Cache Adaptive? A Case Study of Matrix Multiplication and Sorting
  • Zeev Nutov. Data structures for node connectivity queries
  • Soh Kumabe and Yuichi Yoshida. Average sensitivity of the Knapsack Problem
  • Daniel Blankenburg. Resource Sharing Revisited: Local Weak Duality and Optimal Convergence
  • Chris Schwiegelshohn and Omar Ali Sheikh-Omar. An Empirical Evaluation of $k$-Means Coresets
  • Sayan Bhattacharya, Thatchaphol Saranurak and Pattara Sukprasert. Simple Dynamic Spanners with Near-optimal Recourse against an Adaptive Adversary
  • Thijs van der Horst, Maarten Löffler and Frank Staals. Chromatic $k$-Nearest Neighbor Queries
  • Tamal Dey and Tao Hou. Fast Computation of Zigzag Persistence
  • Henk Alkema, Mark de Berg, Leonidas Theocharous and Morteza Monemizadeh. TSP in a Simple Polygon
  • Bento Natura, Meike Neuwohner and Stefan Weltge. The Pareto cover problem
  • Mark Jones, Mathias Weller and Leo van Iersel. Embedding phylogenetic trees in networks of low treewidth
  • Zoe Xi and William Kuszmaul. Approximating Dynamic Time Warping Distance Between Run-Length Encoded Strings
  • Hideo Bannai, Keisuke Goto, Masakazu Ishihata, Shunsuke Kanda, Dominik Köppl and Takaaki Nishimoto. Computing NP-hard Repetitiveness Measures via MAX-SAT
  • Tatsuya Gima, Takehiro Ito, Yasuaki Kobayashi and Yota Otachi. Algorithmic Meta-Theorems for Combinatorial Reconfiguration Revisited
  • Marten Maack, Simon Pukrop and Anna Rodriguez Rasmussen. (In-)Approximability Results for Interval, Resource Restricted, and Low Rank Scheduling
  • Owen Rouille and Clément Maria. Localized geometric moves to compute hyperbolic structures on triangulated 3-manifolds
  • Frederik Brüning, Jacobus Conradi and Anne Driemel. Faster Approximate Covering of Subcurves under the Fréchet Distance
  • Tesshu Hanaka and Michael Lampis. Hedonic Games and Treewidth Revisited
  • Radu Curticapean. Determinants from homomorphisms
  • Raghavendra Addanki, Andrew McGregor and Cameron Musco. Non-Adaptive Edge Counting and Sampling via Bipartite Independent Set Queries
  • Justin Dallant and John Iacono. Conditional Lower Bounds for Dynamic Geometric Measure Problems
  • Maike Buchin, Ivor van der Hoog, Tim Ophelders, Lena Schlipf, Rodrigo Silveira and Frank Staals. Efficient Fréchet distance queries for segments
  • Lex de Kogel, Marc van Kreveld and Jordi L. Vermeulen. Abstract morphing using the Hausdorff distance and Voronoi diagrams
  • Václav Blažej, Pratibha Choudhary, Dušan Knop, Šimon Schierreich, Ondřej Suchý and Tomáš Valla. On Polynomial Kernels for Traveling Salesperson Problem and its Generalizations
  • Yiqiu Wang, Rahul Yesantharao, Shangdi Yu, Laxman Dhulipala, Yan Gu and Julian Shun. ParGeo: A Library for Parallel Computational Geometry
  • Jan Dreier, Sebastian Ordyniak and Stefan Szeider. SAT Backdoors: Depth Beats Size
  • Jakub Gajarský, Lars Jaffke, Paloma Lima, Jana Novotná, Marcin Pilipczuk, Paweł Rzążewski and Uéverton Souza. Taming graphs with no large creatures and skinny ladders
  • Ofer Neiman and Idan Shabat. A Unified Framework for Hopsets
  • Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson and Rico Zenklusen. Submodular Maximization Subject to Matroid Intersection on the Fly
  • Deeparnab Chakrabarty, Maryam Negahbani and Ankita Sarkar. Approximation Algorithms for Continuous Clustering and Facility Location Problems
  • Davide Bilò, Gianlorenzo D’Angelo, Luciano Gualà, Stefano Leucci and Mirko Rossi. Sparse Temporal Spanners with Low Stretch
  • Shahbaz Khan and Alexandru I. Tomescu. Optimizing the Safe Flow Decompositions in DAGs
  • Markus Chimani and Finn Stutzenstein. Spanner Approximations in Practice
  • Wojciech Nadara, Michał Pilipczuk and Marcin Smulewicz. Computing treedepth in polynomial space and linear fpt time
  • Or Zamir. Faster algorithm for Unique (k,2)-CSP
  • Mohammad Ansari, Mohammad Saneian and Hamid Zarrabi-Zadeh. Simple Streaming Algorithms for Edge Coloring

Committees

Chairs

Steering Committee

PC members (Track A)

PC members (Track B)

PC members (Track S)

Invited Speakers

Proceedings

The ESA 2022 proceedings will be published in the Leibniz International Proceedings in Informatics (LIPIcs) series.