SEA 2020

18th Symposium on Experimental Algorithms
June 16-18, 2020
Catania, Italy

18th Symposium on Experimental Algorithms

Welcome to the website of the 18th International Symposium on Experimental Algorithms (SEA 2020) that will be held in Catania (Italy) from the 16th to the 18th of June 2020. SEA (International Symposium on Experimental Algorithms), previously known as Workshop on Experimental Algorithms (WEA), is an international forum for researchers in the area of the design, analysis, and experimental evaluation and engineering of algorithms, as well as in various aspects of computational optimization and its applications.
The Conference will be held at the Benedictine Monastery of “San Nicolò”, a unique place that tells us about the human and historic events of the city on the slope at the foot of Etna, from the ancient times until today.
The proceedings of SEA 2020 will be published in the Leibniz International Proceedings in Informatics (LIPIcs) open-access series. A special issue of selected papers will be published in the ACM Journal of Experimental Algorithmics.

Updates due to COVID19 outbreak

March 2020: the situation surrounding COVID19 outbreak has evolved rapidly and is endangering the health and safety of everyone, which are for us among the highest priorities. Thus, based on the health situation in Italy and around the world, SEA 2020 conference leadership has decided that the most prudent measure is to deliver the conference online to all registered attendees, rather than by a physical meeting.
Thus, we will implement the meeting by an online platform that will provide our attendees around the world a new conference experience. We plan to support audio and video presentations that should be linked to papers. SEA 2020 organizers will be updating the web page and send via email plans for remote participation, as we develop them.

Attending SEA 2020

About Catania
Conference Venue
Travel Information
Social Events
Accomodation
Restaurants
Registration

Important Dates

Extended Deadlines:
Abstract: January 24, 2020
Submission: January 31, 2020
Notification: March 20, 2020
Camera-ready: April 10, 2020
Registration: April 17, 2020
Conference: June 16-18, 2020

"Melior de cinere surgo"

"I am reborn from (my) ashes even more beautiful", the inscription on Porta Ferdinandea, after 1860 entitled Porta Garibaldi, a triumphal arch built in 1768 to commemorate the marriage of King Ferdinand III of Sicily and Maria Carolina of Habsburg-Lorraine. It is located between Piazza Palestro and Piazza Crocifisso, at the end of Via Giuseppe Garibaldi.

About Catania

Catania is the second largest city in Sicily. It is located on the eastern coast of Sicily at the foot of Mount Etna, the biggest volcano in Europe. Its metropolitan area reaches one million inhabitants, being the major transport hub and economic centre in Sicily. It is also a university city where you will enjoy a busy downtown and an active nightlife.
The history of Catania is dating back 2700 years. The city has been dominated by several different cultures, among which Greeks, Romans, Arabs, Normans and Spanish. Thanks to its port, the city has been always a rich commercial centre. Since Catania is situated under the biggest active volcano in Europe, it has been destroyed many times in the past. Moreover, like most of eastern Sicily, after the great earthquake of 1693 Catania has been rebuilt. As a consequence, Catania is a city where you can find a great variety of landscape and architecture. In particular it is well known for its particular baroque architecture and urban design. The downtown area is a World Heritage Site.
One of the best features of Catania is its city centre, rich of Baroque architecture, where you can see beautiful palaces, churches and fountains. The Elephant Statue of the 17th century, in Piazza Duomo, is the symbol of the city. Every morning, except on Sundays, you can walk across two of the most fascinating markets of the city, a large fish market in a beautiful setting off Piazza del Duomo and a bustling food and clothes market off Via Etnea.
During the visit you can make a stop at "the kiosks", which act as social areas for the locals by selling refreshments, such as coffee, Lemoncello or popular unique drinks such as "seltz al limone" or "mandarino al limone". Don't miss to ascend Mount Etna or to relax on the sandy beaches of "La Plaja". You can also visit the "Riviera dei Ciclopi", a rocky volcano coast in the north of the city.

Call for Papers

SEA aims to attract papers from both the Computer Science and the Operations Research/Mathematical Programming communities. The main theme of the symposium is the role of experimentation and of algorithm engineering techniques in the design and evaluation of algorithms and data structures. Submissions should present significant contributions supported by experimental evaluation, methodological issues in the design and interpretation of experiments, the use of (meta-) heuristics, or application-driven case studies that deepen the understanding of the complexity of a problem.

Topics of Interest

Contributions solicited cover a variety of topics including but not limited to:

  • Algorithm Engineering
  • Algorithmic Libraries
  • Algorithmic Mechanism Design
  • Analysis of Algorithms
  • Algorithms for Memory Hierarchies
  • Algorithms for the World-Wide-Web
  • Approximation Techniques
  • Bioinformatics
  • Branch-and-Bound Algorithms
  • Combinatorial and Irregular Problems
  • Combinatorial Structures and Graphs
  • Communication Networks
  • Complex Networks
  • Computational Geometry
  • Computational Learning Theory
  • Computational Optimization
  • Computer Systems
  • Cryptography and Security
  • Data Streams
  • Data Structures
  • Distributed and Parallel Algorithms
  • Evaluation of Algorithms for Realistic Environments
  • Experimental Techniques and Statistics
  • Graph Drawing
  • Heuristics for Combinatorial Optimization
  • Implementation, Testing, Evaluation and Fine-tuning
  • Information Retrieval
  • Integer Programming
  • Logistics and Operations Management
  • Machine Learning and Data Mining
  • Mathematical Programming
  • Metaheuristic Methodologies
  • Multiple Criteria Decision Making
  • Network Analysis
  • Novel Applications of Algorithms in Other Disciplines
  • Online Problems
  • Parallel Algorithms and Computing
  • Railway Optimization using Algorithmic Methods
  • Randomized Techniques
  • Robotics
  • Semidefinite Programming
  • Simulation
  • Software Repositories and Platforms for using Algorithms
  • Telecommunications and Networking

Submission Guidelines

The authors should submit a paper not exceeding 12 pages, including figures, title, authors, affiliations, e-mail addresses, and a short abstract. References will not be counted in the page limit. At least 10-point font should be used. Authors are strongly advised to use the LaTeX style file supplied for the LIPIcs style here. Final proceedings papers must be camera-ready in this format. A clearly marked Appendix, which will not count toward the 12 page submission limit, can be included and will be read at the referees’ discretion. All submissions have to be made via the EasyChair submission page for the conference.
Authors are encouraged to include a link to the source code and/or datasets to increase confidence in the reproducibility of their experiments; the code may be read and/or executed at the referees' discretion.
Papers submitted for review should represent original, previously unpublished work or surveys of important results. At the time the paper is submitted to SEA, and for the entire review period, the paper (or essentially the same paper) should not be under review by any other conference with published proceedings or by a scientific journal. At least one author of each accepted paper will be expected to attend the conference and present the paper.
At the time of submission authors are required to specify the track to which they want submit their paper. The indication of the track should be entered as the first line of the abstract. The conference tracks are listed below.

The abstract must be submitted by January 24, 2020, AoE (extended deadline)
The full paper must be submitted by January 31, 2020, AoE (extended deadline)

Proceedings and Special Issue

The conference proceedings will be published in the Leibniz International Proceedings in Informatics (LIPIcs), a series of high-quality conference proceedings across all fields in informatics established in cooperation with Schloss Dagstuhl Leibniz Center for Informatics. SEA Proceedings volumes are published according to the principle of OpenAccess, i.e., they are available online and free of charge.
Since SEA 2008 a special issue of selected papers accepted at the conference is published in the ACM Journal of Experimental Algorithmics.

Conference Tracks

SEA aims to attract papers from both the Computer Science and the Operations Research/Mathematical Programming communities. Submissions should present significant contributions supported by experimental evaluation, methodological issues in the design and interpretation of experiments, the use of (meta-) heuristics, or application-driven case studies that deepen the understanding of the complexity of a problem.
SEA calls papers for a main general track, covering the above concepts, and two specific tracks, covering aspects of string processing and aspects of graph theory, as presented below.

This track covers the main themes of the symposium and specifically the role of experimentation and of algorithm engineering techniques in the design and evaluation of algorithms and data structures. Topics include but are not restricted to: approximation techniques, bioinformatics, branch-and-bound algorithms, combinatorial problems, combinatorial structures, computational geometry, computational optimization, cryptography and Security, information retrieval, machine learning and data mining, parallel algorithms, randomized techniques, simulation,
This track covers research in all aspects of experimental algorithms on string processing, including but not restricted to: algorithms for pattern matching in strings, text indexing, data structures for string processing, coding and text compression, compressed data structures, compressed string processing, text mining, 2D pattern matching, automata based string processing, searching for regularities and support of the above concepts by suitable implementations and applications.
This track covers research in all aspects of experimental algorithms on graphs, including but not restricted to: design and analysis of sequential, parallel, randomized, parameterized algorithms on graphs, distributed graph and network algorithms, structural graph theory with algorithmic or complexity applications, computational complexity of graph and network problems, graph grammars, graph rewriting systems and graph modeling, graph drawing and layouts, graph mining, random graphs and models of the web and scale-free networks, and support of the above concepts by suitable implementations and applications.

At the time of submission authors are required to specify the track to which they want submit their paper. The indication of the track should be entered as the first line of the abstract (e.g. Track 02: Experimental Algorithms on Strings)

Invited Speakers
Text indexing is a classical algorithmic problem that has been studied for over four decades. The earliest optimal-time solution to the problem, the suffix tree, dates back to 1973 but requires one order of magnitude more space than the text to be stored. In the year 2000, two breakthrough works showed that this space overhead is not necessary: both the index and the text can be stored in a space proportional to the text's entropy. These contributions had an enormous impact in bioinformatics: nowadays, virtually any DNA aligner employs compressed indexes. In recent years, it became apparent that entropy had reached its limits: modern datasets (for example, collections of thousands of human genomes) are extremely large but very repetitive and, by its very definition, entropy cannot compress repetitive texts. To overcome this problem, a new generation of indexes based on dictionary compressors (for example, LZ77 and run-length BWT) emerged, together with generalizations of the indexing problem to labeled graphs. This talk is a survey of the landmarks of this fascinating path that took us from suffix trees to the most modern compressed indexes on graphs.
Several decades ago, in the spring days of computer science Donald E. Knuth and Kurt Mehlhorn both dedicated a book of their monographs to the topic of sorting and searching. Since then, driven by the advances in computer hardware technology there have been several proposals to engineer the set of fundamental algorithms. One aspect we look at is improving locality of disk access and cache access, another one efficiency tuning by reducing the number of branch mispredictions. We also will look at leading factors hidden in Landau's Big-Oh notation to study how far searching and sorting algorithms are from their respective lower bounds. These studies in algorithm engineering, in turn, lead to exiting new algorithm designs. On the practical side, we will establish that efficient sorting and searching algorithms are in tight collaboration, as sorting is used for finding duplicates in disk-based search, and new heap structures designed for efficient graph search can be exploited in classical and adaptive sorting. We indicate the effects engineered sorting and searching for combined task and motion planning in robotics applications.
Conference Committees
Domenico Cantone (chair), University of Catania (Italy)
Simone Faro (chair), University of Catania (Italy)
Pietro Maugeri, University of Catania (Italy)
Daniele Francesco Santamaria, University of Catania (Italy)
Golnaz Badkobeh, Goldsmiths University of London (UK)
Gianfranco Bilardi, University of Padova (Italy)
Christina Boucher, University of Florida (USA)
Domenico Cantone (chair), University of Catania (Italy)
Pierluigi Crescenzi, Université de Paris-IRIF (France)
Maxime Crochemore, Kings College London (UK)
Simone Faro (chair), University of Catania (Italy)
Paola Festa, University of Naples Federico II (Italy)
Irene Finocchi, Sapienza University of Rome (Italy)
Travis Gagie, Dalhousie University (Canada)
Arie Koster, RWTH Aachen University (Germany)
Oguzhan Kulekci, Istanbul Technical University (Turkey)
Susana Ladra, University of A Coruña (Spain)
Thierry Lecroq, University of Rouen Normandy (France)
Veli Mäkinen, University of Helsinki (Finland)
Petra Mutzel, TU Dortmund (Germany)
Gonzalo Navarro, University of Chile (Chile)
Panos Pardalos, University of Florida (USA)
Nadia Pisanti, University of Pisa (Italy)
Ely Porat, Bar-Ilan University (Israel)
Simon J. Puglisi, University of Helsinki (Finland)
Ilya Razenshteyn, Microsoft Research (USA)
Mauricio Resende, Amazon.com Inc. (USA)
Marie-France Sagot, INRIA (France)
Alessandra Sala, Bell Labs (Ireland)
Peter Sanders, Karlsruhe Institute of Technology (Germany)
Stefan Schmid, University of Vienna (Austria)
Sabine Storandt, Universität Konstanz (Germany)
Dorothea Wagner, Karlsruhe Institute of Technology (Germany)
Renato Werneck, Amazon.com Inc. (USA)
Weili Wu, University of Texas at Dallas (USA)
Edoardo Amaldi, Politecnico di Milano (Italy)
David A. Bader, New Jersey Institute of Technology (US)
Josep Diaz, Universitat Politecnica de Catalunya (Spain)
Giuseppe F. Italiano, University of Rome Tor Vergata (Italy)
Klaus Jansen, University of Kiel (Germany)
Kurt Mehlhorn, Max-Planck-Institut für Informatik (Germany)
Ian Munro, University of Waterloo (Canada)
Sotiris Nikoletseas, Patras University (Greece)
Jose Rolim, University of Geneva (Switzerland)
Pavlos Spirakis, University of Liverpool (UK)
Accepted Papers

M. Fonseca Faraj, A. van der Grinten, H. Meyerhenke, J. Larsson Träff and C. Schulz
High-Quality Hierarchical Process Mapping

S. Fekete, A. Hill, D. Krupke, T. Mayer, J. Mitchell, O. Parekh and C. Phillips
Probing a Set of Trajectories to Maximize Captured

K. Matsuda, S. Denzumi and K. Sadakane
Storing Set Families More Compactly with Top ZDDs

D. Köppl, S. Puglisi and R. Raman
Fast and Simple Compact Hashing via Bucketing

D. Berend and Y. Twitto
Effect of Initial Assignment on Local Search Performance for Max Sat

Y. Nakahata, M. Nishino, J. Kawahara and S. Minato
Enumerating All Subgraphs under Given Constraints Using Zero-suppressed Sentential Decision Diagrams

L. Gottesbüren, M. Hamann, P. Schoch, B. Strasser, D. Wagner and S. Zühlsdorf
Engineering Exact Quasi-Threshold Editing

L. Gottesbüren, M. Hamann, S. Schlag and D. Wagner
Advanced Flow-Based Multilevel Hypergraph Partitioning

Z. Liptak, S. Puglisi and M. Rossi
Pattern Discovery in Colored Strings

S. Kobayashi, D. Hendrian, R. Yoshinaka and A. Shinohara
Fast and linear-time string matching algorithms based on the distances of q-gram occurrences

K. Hanauer, M. Henzinger and C. Schulz
Faster Fully Dynamic Transitive Closure in Practice

T. Maier, P. Sanders and R. Williger
Concurrent Expandable AMQs on the Basis of Quotient Filters

J. Sauer, D. Wagner and T. Zündorf
Faster Multi-Modal Route Planning with Bike Sharing Using ULTRA

A. Kleff, F. Schulz, J. Wagenblatt and T. Zeitz
Efficient Route Planning with Temporary Driving Bans, Road Closures, and Rated Parking Areas

A. Al Zoobi, D. Coudert and N. Nisse
Space and time tradeoffs for the k shortest simple paths problem

J. Trimble
An Algorithm for the Exact Treedepth Problem

F. Cooper and D. Manlove
Algorithms for new types of fair stable matchings

D. Antypov, A. Deligkas, V. Gusev, M. Rosseinsky, P. Spirakis and M. Theofilatos
Crystal Structure Prediction via Oblivious Local Search

K. Nakamura, S. Denzumi and M. Nishino
Variable Shift SDD: A More Succinct Sentential Decision Diagram

E. Kuthe and S. Rahmann
Engineering Fused Lasso Solvers on Trees

S. Moghtasedi, R. Grossi and A. Marino
Finding Structurally and Temporally Similar Trajectories in Graphs

L. Barth and D. Wagner
Zipping Segment Trees

V. Buchhold, D. Delling, D. Schieferdecker and M. Wegner
Fast and Stable Repartitioning of Road Networks

M. He and S. Kazi
Path Query Data Structures in Practice

Registration

Based on the current health situation in Italy and around the world, SEA 2020 conference leadership has decided that the most prudent measure is to deliver the conference online to all registered attendees, rather than by a physical meeting.
As a consequence, registration fees for authors and attendees will be discounted.
SEA 2020 registration policy requires that at least one author per paper should register at the conference to guarantee, at least, the conference cost coverage (thus one registration will give the right to present only one paper).
Fees reported below comprise remote access to all sessions and one electronic copy of the proceedings volume.

Presenting Author Registration

Deadline: April 17, 2020
Fee: 240 Euros

Attendee Registration

Deadline: June 3, 2020
Fee: 140 Euros




Payment

All payments are to be made through a wire transfer to the following bank accont:

Beneficiary: Associazione IPLab
Beneficiary Address: c/o Dipartimento di Matematica e Informatica, viale A. Doria 6, 95125 Catania (Italy)
Beneficiary Fiscal Code: 93183000871
Bank: Banca Generali s.p.a Sede operativa Trieste
Bank Address: corso Cavour 5/A - 34132 Trieste
BIC SWIFT CODE: BGENIT2T
IBAN: IT 05 Z 03075 02200 CC8500483136

Please specify in the Memo Line the following: NAME SURNAME + SEA 2020 Registration
Replace NAME and SURNAME with your full name and put them as Initial strings. This is crucial in order to have your payment properly traced, since some banks cut the string to a small number of characters.

A copy of the wire tranfer must be sent by email to sea2020@easychair.org
We remark that the registration is not complete until the fees have been received. The date that defines the fees applicable is when the payment is executed. An acknowledged of the registration to the conference will be sent by email after the payment is received.

Registration Form

For your registration, please, provide your contact information by filling the following form:

Workshop Program

The workshop will last three days, from 16 to 18 June 2018. The first talk of each working day will be held by an invited spekear on topics of interest to the active community in the field of experimental algorithms. The authors of accepted papers at the conference will have a thirty-minute slot for their talks.
The workshop will also include the participation of guests in a social dinner and a social event that will allow them to get to know the beauty of the Etna area.
The final program of SEA 2020 will be posted at the end of April 2020.

The Benedictine Monastery of “San Nicolò”.

The Conference will be hold at the Benedictine Monastery of “San Nicolò”, a unique place that tells about the human and historic events of the city on the slope at the foot of Etna, from the ancient times until today.
The monastery was founded in 1558, it's complex is located in the historical centre of the city of Catania, with the church of San Nicolò l'Arena. It shows architectonical integration of many styles through different centuries. Although the monastery was founded in the 16th century, it was modified by two natural disasters in the 17th century.
In 1977 the monastery was donated to the University of Catania, which restored the entire structure and nowdays it hosts the Department of Humanities of the University of Catania and is 10 minutes walk from the Cathedral square. It is a late baroque monument and one of the biggest Benedictine monastery in Europe. The construction of the building started in 1500 and has continued until today.
It is an example of architectonical integration of different styles through different epochs: you can find a roman house, the cloisters and a roof garden. The monastery is a UNESCO World Heritage Site.

Web site Virtual tour
Travel Informations
How to Reach the Central Piazza Duomo

It’s not so difficult to reach Piazza Duomo, the central square of Catania, if you come from the surrounding areas and it’s much easier than moving from a part of town to another one, unless your destination is close to one of the few but efficient subway stops.

From Fontanarossa-Airport Vincenzo Bellini to the City Center
If you come by plane, then it’s superfast and easy. Alibus is a special city line serving the city center from Catania Airport. You can catch it right at the exit of Vincenzo Bellini airport. There’s one every 25 minutes and it gets right into the heart of Catania in about 10 minutes for a €4 ticket that you can buy on the bus itself. Jump down at the stop named Archi, follow the marine arches to the left and in a five minutes walk you’ll be in Piazza Duomo and at the fish market. Alibus goes on for other 14 stops, reaching after Archi the Central Station and then the most central areas of Catania before going back to the airport and start a new ride. Here’s a link to its map.

From Catania Central Station to the City Center
The central station is at a quite short walk to the city center and just one subway stop away from via Etnea and piazza Stesicoro, where many city buses stops going almost everywhere. Central Station and Piazza Stesicoro are in fact two of the main hubs for city buses. If you wish to reach Piazza Duomo, just cross the street when you walk out of the station and walk to the left side of the square where you’ll see an orange sign for the bus stop Stazione Ovest, Catch number 2-5 and jump down at the stop Civita, or S.Placido or Borsellino. Otherwise, you can just walk for 15 minutes on the Passiaturi, a beautiful prom in town, passing by the railway and the sea.

Taxi Service
RadioTaxi Catania tel. +39 095 333216 - +39 095 330966
RadioTaxi tel. +39 095 241911

Università Degli Studi di Catania
GNCS INDAM
Algorithms by MDPI
History
Previous SEA (and WEA) Conferences

The International Symposium on Experimental Algorithms (SEA) was previously known, until 2008, as Workshop on Experimental Algorithms (WEA). It is an international forum for researchers in the area of the design, analysis, and experimental evaluation and engineering of algorithms, started in 2001 at Riga, Latvia.

SEA 2018, L'Aquila, Italy
SEA 2017, London, UK
SEA 2016, Petersburg, Russia
SEA 2015, Paris, France
SEA 2014, Copenhagen, Denmark
SEA 2013, Rome Italy
SEA 2012, Bordeaux, France
SEA 2011, Crete, Greece
SEA 2010, Ischia Island, Italy
SEA 2009, Dortmund, Germany
WEA 2008, Cape Cod, USA
WEA 2007, Rome, Italy
WEA 2006, Menorca Island, Spain
WEA 2005, Santorini, Greece
WEA 2004, Angra dos Reis, Rio de Janeiro, Brazil
WEA 2003, Monte Verità, Ascona, Switzerland
WEA 2001, Riga, Latvia

   
SEA (and WEA) Proceedings

From 2001 to 2016 the prooceedings of SEA (and WEA) were published by Springer Verlag in a volume of Lecture Notes in Computer Science (see proceedings timelines). Since 2017 the proceedings of SEA are published in the Leibniz International Proceedings in Informatics (LIPIcs), a series of high-quality conference proceedings across all fields in informatics established in cooperation with Schloss Dagstuhl Leibniz Center for Informatics.

SEA 2018, ISBN 978-3-95977-070-5, LIPICS Vol.103
SEA 2017, ISBN 978-3-95977-036-1, LIPICS Vol.75
SEA 2016, ISBN 978-3-319-38851-9, LNCS Vol.9685
SEA 2015, ISBN 978-3-319-20085-9, LNCS Vol.9125
SEA 2014, ISBN 978-3-319-07959-2, LNCS Vol.8504
SEA 2013, ISBN 978-3-642-38527-8, LNCS Vol.7933
SEA 2012, ISBN 978-3-642-30850-5, LNCS Vol.7276
SEA 2011, ISBN 978-3-642-20662-7, LNCS Vol.6630
SEA 2010, ISBN 978-3-642-13193-6, LNCS Vol.6049
SEA 2009, ISBN 978-3-642-02011-7, LNCS vol.5526
WEA 2008, ISBN 978-3-540-68548-7, LNCS Vol.5038
WEA 2007, ISBN 978-3-540-72844-3, LNCS Vol.4525
WEA 2006, ISBN 978-3-540-34597-8, LNCS Vol.4007
WEA 2005, ISBN 978-3-540-25920-6, LNCS Vol.3503
WEA 2004, ISBN 978-3-540-22067-1, LNCS Vol.3059
WEA 2003, ISBN 978-3-540-40205-3, LNCS Vol.2647