The Organization Committee (OC) and the Chairs of ALGO 2020 decided to run the conferences online in a virtual way. What is most important is that the scientific activity of the Programme Committees of the ALGO conferences is not suspended or stopped: peer review, accepted papers, camera ready and proceedings will be accomplished as usual. Instructions for authors on how to give their talks online in the virtual room will be provided.

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 2020.

Important Dates

  • Paper submission deadline: April 24, 2020, April 29, 2020 (23:59 AoE)
  • Notification: June 18, 2020
  • Camera ready: June 28, 2020
  • Conference: September 7 - 9, 2020, in Pisa, Italy

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. 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. ESA 2020 proceedings will be published in the Leibniz International Proceedings in Informatics (LIPIcs) series, based at Schloss Dagstuhl. The proceedings chair is Grzegorz Herman, Jagiellonian University, Poland.

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 both tracks of ESA 2020, 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 2020, 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
  • 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

COMMITTEES

Chairs

Steering Committee

PC Members (track A)

  • Amir Abboud, IBM Almaden Research Center
  • Gregory Bodwin, Georgia Tech
  • Karl Bringmann, MPII
  • Deeparnab Chakrabarty, Dartmouth College
  • Daniel Dadush, CWI
  • Michael Elkin, Ben-Gurion University of the Negev
  • Leah Epstein, University of Haifa
  • Manuela Fischer, ETHZ
  • Fabrizio Frati, Roma Tre University
  • Fabrizio Grandoni (chair), IDSIA
  • Kasper Green Larsen, Aarhus University
  • Jacob Holm, University of Copenhagen
  • Michael Kapralov, EPFL
  • Petteri Kaski, Aalto University
  • Telikepalli Kavitha, TIFR
  • Tomasz Kociumaka, Bar-Ilan University
  • Moshe Lewenstein, Bar-Ilan University
  • Shi Li, University at Buffalo
  • Yury Makarychev, TTIC
  • Krzysztof Onak, IBM T.J. Watson Research Center
  • Seth Pettie, University of Michigan
  • Marcin Pilipczuk, University of Warsaw
  • Thomas Rothvoss, University of Washington
  • Laura Sanità, University of Waterloo
  • Saket Saurabh, Institute of Mathematical Sciences
  • Chris Schwiegelshohn, Sapienza University of Rome
  • Vera Traub, ETHZ
  • Carmine Ventre, King's College London
  • David Wajc, Carnegie Mellon University
  • Andreas Wiese, Universidad de Chile
  • David P. Woodruff, Carnegie Mellon University
  • Meirav Zehavi, Ben-Gurion University of the Negev

PC Members (track B)

  • Armin Biere, Linz University
  • Maike Buchin, Bochum University
  • Markus Chimani, University of Osnabrück
  • Irene Finocchi, LUISS University, Rome
  • Travis Gagie, Dalhousie University
  • Rolf Niedermeier, TU Berlin
  • Kunihiko Sadakane, University of Tokyo
  • Peter Sanders (chair), KIT Karlsruhe
  • Yihan Sun, UC Riverside
  • Sivan Toledo, Tel-Aviv University
  • Jesper Träff, TU Vienna
  • Renato Werneck, Amazon

Accepted papers

TRACK A

A $(1-e^{-1}-\epsilon)$-Approximation for the Monotone Submodular Multiple Knapsack Problem
Yaron Fairstein, Ariel Kulik, Joseph Seffi Naor, Danny Raz, Hadas Shachnai

A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time
Zachary Friggstad, Chaitanya Swamy

A linear fixed parameter tractable algorithm for connected pathwidth
Mamadou Moustapha Kanté, Christophe Paul, Dimitrios Thilikos

A Polynomial Kernel for Line Graph Deletion
Eduard Eiben, William Lochet

A Sub-linear Time Framework for Geometric Optimization with Outliers in High Dimensions
Hu Ding

AcyclicStar and Injective Colouring: A Complexity Picture for H-Free Graphs
Jan Bok, Nikola Jedličková, Barnaby Martin, Daniel Paulusma, Siani Smith

An Algorithmic Meta-Theorem for Graph Modification to Planarity and FOL
Fedor Fomin, Petr Golovach, Giannos Stamoulis, Dimitrios Thilikos

An algorithmic weakening of the Erdős-Hajnal conjecture
Édouard Bonnet, Stéphan Thomassé, Xuan Thang Tran, Rémi Watrigant

An Optimal Decentralized $(\Delta + 1)$-Coloring Algorithm
Daniel Bertschinger, Johannes Lengler, Anders Martinsson, Robert Meier, Angelika Steger, Milos Trujic, Emo Welzl

Analysis of the Period Recovery Error Bound
Amihood Amir, Itai Boneh, Michael Itzhaki, Eitan Kondratovsky

Approximate $CVP_\infty$ in time $2^{0.802 n}$
Moritz Venzin, Friedrich Eisenbrand

Approximate Turing Kernelization for Problems Parameterized by Treewidth
Eva-Maria Hols, Stefan Kratsch, Astrid Pieterse

Approximating k-connected m-dominating sets
Zeev Nutov

Approximation Algorithms for Clustering with Dynamic Points
Shichuan Deng, Jian Li, Yuval Rabani

Augmenting the Algebraic Connectivity of Graphs
Bogdan Manghiuc, Pan Peng, He Sun

Capacitated Sum-of-Radii Clustering: An FPT Approximation
Tanmay Inamdar, Kasturi Varadarajan

Chordless Cycle Packing is Fixed-Parameter Tractable
Dániel Marx

Compact Oblivious Routing in Weighted Graphs
Philipp Czerner, Harald Räcke

Coresets for the Nearest-Neighbor Rule
Alejandro Flores-Velazco, David Mount

Cutting Polygons into Small Pieces with Chords: Laser-Based Localization
Esther Arkin, Rathish Das, Jie Gao, Mayank Goswami, Joseph Mitchell, Valentin Polishchuk, Csaba Toth

Distance bounds for high dimensional consistent digital rays and 2-D partially-consistent digital rays
Man Kwun Chiu, Matias Korman, Martin Suderland, Takeshi Tokuyama

Dual Half-integrality for Weakly-supermodular Cut Cover and its Application to Maximum Half-Integral Flow
Naveen Garg, Nikhil Kumar

Efficient Computation of 2-Covers of a String
Jakub Radoszewski, Juliusz Straszyński

Exploiting c-Closure in Kernelization Algorithms for Graph Problems
Tomohiro Koana, Christian Komusiewicz, Frank Sommer

Fast Preprocessing for Optimal Orthogonal Range Reporting and Range Successor with Applications to Text Indexing
Younan Gao, Meng He, Yakov Nekritch

Finding large $H$-colorable subgraphs in hereditary graph classes
Maria Chudnovsky, Jason King, Michał Pilipczuk, Paweł Rzążewski, Sophie Spirkl

Fine-Grained Complexity of Regular Expression Pattern Matching and Membership
Philipp Schepper

First-Order Model-Checking in Random Graphs and Complex Networks
Jan Dreier, Philipp Kuinke, Peter Rossmanith

Full complexity classification of the list homomorphism problem for bounded-treewidth graphs
Karolina Okrasa, Marta Piecyk, Paweł Rzążewski

Fully-Dynamic Coresets
Monika Henzinger, Sagar Kale

Grundy Distinguishes Treewidth from Pathwidth
Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi

Improved Algorithms for Alternating Matrix Space Isometry: from Theory to Practice
Peter A. Brooksbank, Yinan Li, Youming Qiao, James B. Wilson

Improved Approximation Algorithm for Set1Multicover with Non-Piercing Regions
Rajiv Raman, Saurabh Ray

Improved Bounds for Metric Capacitated Covering Problems
Sayan Bandyapadhyay

Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time
Hanlin Ren

Improved Prophet Inequalities for Combinatorial Welfare Maximization with (Approximately) Subadditive Agents
Hanrui Zhang

Incompressibility of H-free edge modification problems: Towards a dichotomy
Dániel Marx, R. B. Sandeep

Kernelization of Witney Switches
Fedor Fomin, Petr Golovach

Light Euclidean Spanners with Steiner Points
Hung Le, Shay Solomon

Linear Expected Complexity for Directional and Multiplicative Voronoi Diagrams
Chenglin Fan, Benjamin Raichel

Linear Time LexDFS on Chordal Graphs
Jesse Beisegel, Ekkehard Köhler, Robert Scheffler, Martin Strehler

Lower Bounds and Approximation Algorithms for Search Space Sizes in Contraction Hierarchies
Johannes Blum, Sabine Storandt

Many visits TSP revisited
Lukasz Kowalik, Shaohua Li, Wojciech Nadara, Marcin Smulewicz, Magnus Wahlström

Mincut Sensitivity Data Structures for the Insertion of an Edge
Surender Baswana, Till Knollmann, Shiv Gupta

Minimum Neighboring Degree Realization in Graphs and Trees
Amotz Bar-Noy, Keerti Choudhary, Avi Cohen, David Peleg, Dror Rawitz

More on Change-Making and Related Problems
Timothy M. Chan, Qizheng He

New Binary Search Tree Bounds via Geometric Inversions
Parinya Chalermsook, Wanchote Jiamjitrak

New Bounds on Augmenting Steps of Block-structured Integer Programs
Lin Chen, Martin Koutecky, Lei Xu, Weidong Shi

Noisy, Greedy and Not So Greedy k-means++
Anup Bhattacharya, Jan Eube, Heiko Röglin, Melanie Schmidt

On Compact RAC Drawings
Henry Förster, Michael Kaufmann

On the Approximation Ratio of the $k$-Opt and Lin-Kernighan Algorithm for Metric and Graph TSP
Xianghui Zhong

On the Complexity of BWT-runs Minimization via Alphabet Reordering
Jason Bentley, Daniel Gibney, Sharma V. Thankachan

On the Complexity of Recovering Incidence Matrices
Ramanujan M. Sridharan, Pranabendu Misra, Petr Golovach, Fedor Fomin

On the Computational Complexity of Linear Discrepancy
Lily Li, Aleksandar Nikolov

Optimal Polynomial-time Compression for Boolean Max CSP
Bart Jansen, Michal Wlodarczyk

Optimally handling commitment issues in online throughput maximization
Franziska Eberle, Nicole Megow, Kevin Schewior

Parallel Batch-dynamic Trees via Change Propagation
Umut Acar, Daniel Anderson, Guy Blelloch, Laxman Dhulipala, Sam Westrick

Planar Bichromatic Bottleneck Spanning Trees
A. Karim Abu-Affash, Sujoy Bhore, Paz Carmi, Joseph Mitchell

Polynomial Time Approximation Schemes for Clustering in Low Highway Dimension Graphs
Andreas Emil Feldmann, David Saulpic

Reconfiguration of Spanning Trees with Many or Few Leaves
Nicolas Bousquet, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki, Kunihiro Wasa

Set Cover with Delay - Clairvoyance is not Required
Yossi Azar, Ashish Chiplunkar, Shay Kutten, Noam Touitou

Settling the relationship between Wilber's bounds for dynamic optimality
Victor Lecomte, Omri Weinstein

Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs
Panagiotis Charalampopoulos, Adam Karczmarz

Sometimes Reliable Spanners of Almost Linear Size
Kevin Buchin, Sariel Har-Peled, Dániel Oláh

Subexponential parameterized algorithms and kernelization on almost chordal graphs
Fedor Fomin, Petr Golovach

The Fine-grained Complexity of Median and Center String Problems under Edit Distance
Gary Hoppenworth, Jason Bentley, Daniel Gibney, Sharma V. Thankachan

The Maximum Binary Tree Problem
Karthekeyan Chandrasekaran, Elena Grigorescu, Gabriel Istrate, Shubhang Kulkarni, Young-San Lin, Minshen Zhu

The Minimization of Random Hypergraphs
Thomas Bläsius, Tobias Friedrich, Martin Schirneck

The number of repetitions in 2D-strings
Panagiotis Charalampopoulos, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen, Wiktor Zuba

Tight Approximation Algorithms for p-Mean Welfare Under Subadditive Valuations
Siddharth Barman, Umang Bhaskar, Anand Krishna, Ranjani Sundaram 


TRACK B

An Algorithmic Study of Fully Dynamic Independent Sets for Map Labeling
Sujoy Bhore, Guangping Li, Martin Nöllenburg

An Efficient, Practical Algorithm and Implementation for Computing Multiplicatively Weighted Voronoi Diagrams
Martin Held, Stefan de Lorenzo

Approximation of the Diagonal of a Laplacian's Pseudoinverse for Complex Network Analysis
Eugenio Angriman, Alexander van der Grinten, Maria Predari, Henning Meyerhenke

Dynamic Matching in Practice
Monika Henzinger, Shahbaz Khan, Richard Paul, Christian Schulz

Engineering fast almost optimal algorithms for bipartite graph matching
Ioannis Panagiotas, Bora Uçar

Finding All Global Minimum Cuts In Practice
Monika Henzinger, Alexander Noe, Christian Schulz, Darren Strash

Generalizing CGAL Periodic Delaunay Triangulations
Georg Osang, Mael Rouxel-Labbé, Monique Teillaud

Kruskal-based approximation algorithm for the multi-level Steiner tree problem
Reyan Ahmed, Faryad Darabi Sahneh, Keaton Hamm, Stephen Kobourov, Richard Spence

Practical Performance of Space Efficient Data Structures for Longest Common Extensions
Patrick Dinklage, Johannes Fischer, Alexander Herlez, Tomasz Kociumaka, Florian Kurpicz

Reconstructing Biological and Digital Phylogenetic Trees in Parallel
Ramtin Afshar, Pedro Matias, Michael Goodrich, Martha Osegueda

Simulating Population Protocols in Sub-Constant Time per Interaction
Petra Berenbrink, David Hammer, Dominik Kaaser, Ulrich Meyer, Manuel Penschuck, Hung Tran.

Space-efficient, Fast and Exact Routing in Time-dependent Road Networks
Ben Strasser, Dorothea Wagner, Tim Zeitz

When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance under Translation
Karl Bringmann, Marvin Künnemann, André Nusser
	      

Invited Speakers (TBA)

Name Lastname

Affiliation

Short CV

Name Lastname

Affiliation

Short CV

Name Lastname

Affiliation

Short CV

Proceedings

ESA 2020 proceedings will to be available in the Leibniz International Proceedings in Informatics (LIPIcs) series, at the beginning of the conference.