Instructions

The Organizing Committee (OC) arranged ALGO 2020 to foster interaction among attendants and speakers during the talks, hopefully providing more benefit than a simple streaming. For this, the OC needed to implement some ideas suggested by the Chairs, taking into consideration a shorter time span for each day, so as people outside Europe could attend due to different time zones.

Please read [the instructions in this link] to get a better experience with the virtual conferences in ALGO 2020.

Programme

Quick link to daily schedule of ALGO 2020, please click below:
MONDAY, Sept. 7 TUESDAY, Sept. 8 WEDNESDAY, Sept. 9 THURSDAY, Sept. 10 PLENARY SPEAKERS

Quick link to each conference programme of ALGO 2020, please click below:
ALGOSENSORS ATMOS ESA (tracks A and B) WABI WAOA

Daily Schedule (CEST, Rome, Italy)

Each time slot can be derived by the union of time intervals reported in the first column. For example the time slot of "WABI: Session 2" is 15:00-16:00, that of "ESA: Poster session 3" is 15:30 - 16:30, and that of "ATMOS: Session 6" is 14:00 - 15:30. All the beginnings of talks in each session are at multiples of 30 minutes (except for ATMOS: Session 1).

Monday, September 7, 2020. Unsure about Italy time zone? [Please check here].
11:45 - 12:45ATMOS: Session 1
12:45 - 13:00Greetings from the Rector of the University of Pisa (ALGO Plenary Room)
13:00 - 14:00ESA: Poster session 1ATMOS: Session 2
WABI: Opening (13:45)
14:00 - 15:00ESA: Poster session 2WABI: Session 1ATMOS: Session 3
15:00 - 15:30ESA: Best student paper track AWABI: Session 2
15:30 - 16:00ESA: Poster session 3ATMOS: Session 4
16:00 - 16:30WABI: Invited speaker (E. Garrison)
16:30 - 17:00BREAK
17:00 - 18:00ALGO: Plenary speaker (R. Rubinfeld)
18:00 - 18:30ESA social junior-seniorWABI: Session 3ATMOS: Invited speaker (T. Horstmannshoff)
18:30 - 19:00ATMOS: Best paper
19:00 - 19:15ATMOS: Business meeting
Tuesday, September 8, 2020. Unsure about Italy time zone? [Please check here].
12:00 - 13:00ATMOS: Session 5
13:00 - 14:00ALGO: Plenary speaker (M. Savelsbergh)
14:00 - 15:00ESA: Poster session 4WABI: Session 4ATMOS: Session 6
15:00 - 15:30
ESA: Best paper track B
WABI: Session 5
15:30 - 16:00ESA: Poster session 5ATMOS: Session 7
16:00 - 16:30 WABI: invited speaker (V. Boeva)
16:30 - 17:00 BREAK
17:00 - 18:00ESA: Test-of-time awardWABI: Session 6
18:00 - 19:00ESA: Social junior-seniorWABI: Session 7
Wednesday, September 9, 2020. Unsure about Italy time zone? [Please check here].
12:00 - 13:00WAOA: Session 1
13:00 - 14:00ESA: Poster session 6WAOA: Session 2
14:00 - 15:00ESA: Poster session 7WABI: Session 8WAOA: Session 3ALGOSENSORS: Session 1
15:00 - 15:30
ESA: Best paper track A
15:30 - 16:30ESA: Poster session 8WABI: Session 9WAOA: Session 4ALGOSENSORS: Session 2
16:30 - 17:00
BREAK
17:00 - 18:00ALGO: Plenary speaker (D. Gusfield)
18:00 - 19:00
ALGO: Business meeting (ALGO Plenary Room)
19:00 - 20:00
ESA: Business meetingWABI: Community meetingALGOSENSORS: Business meeting
Thursday, September 10, 2020. Unsure about Italy time zone? [Please check here].
12:00 - 12:30ALGOSENSORS: Session 3
12:30 - 13:30WAOA: Session 5
13:30 - 14:30ALGO: Plenary speaker (P. Fraigniaud)
14:30 - 15:30WAOA: Session 6ALGOSENSORS: Session 4
15:30 - 16:30WAOA: Session 7ALGOSENSORS: Session 5
16:30 - 17:00BREAK
17:00 - 18:00ALGO: Plenary speaker (C. Stein)
18:00 - 18:15Farewell

ALGO 2020 Plenary Speakers

Location: MS Teams "ALGO Plenary Room". Unsure about Italy time zone? [Please check here].


ALGO: Plenary Speaker (Monday, Sept. 7, 17:00-18:00, Chair Fabrizio Grandoni)
Local Computation Algorithms [click for live event]
Ronitt Rubinfeld, CSAIL, MIT, Cambridge, USA
Consider a setting in which inputs to and outputs from a computational problem are so large, that there is not time to read them in their entirety. However, if one is only interested in small parts of the output at any given time, is it really necessary to solve the entire computational problem? Is it even necessary to view the whole input? We survey recent work in the model of "local computation algorithms" which for a given input, supports queries by a user to values of specified bits of a legal output. The goal is to design local computation algorithms in such a way that very little of the input needs to be seen in order to determine the value of any single bit of the output. Though this model describes sequential computations, techniques from local distributed algorithms have been extremely important in designing efficient local computation algorithms. In this talk, we describe results on a variety of problems for which sublinear time and space local computation algorithms have been developed -- we will give special focus to finding maximal independent sets and generating random objects.

ALGO: Plenary Speaker (Tuesday, Sept. 8, 13:00-14:00, Chair Dennis Huisman)
Algorithms for Large-Scale Service Network Design and Operations [click for live event]
Martin Savelsbergh, Georgia Tech, USA
Consolidation carriers, such as package express companies and less-than-truckload companies, employ a hub-and-spoke network to move shipments from their origins to their destinations. Shipments are sorted and consolidated at the terminals to ensure high utilization of the vehicles moving shipments between terminals. We discuss computationally efficient and effective algorithms for two problems arising in this context. First, determining a load and flow plan, i.e., when and where to operate vehicles in the network and how to route shipments through the network. Second, given a load and flow plan how to make adjustments on the day of operations to efficiently and effectively react to deviations from expected shipment volumes (which were used to create the load and flow plan). The focus will be on algorithms that can handle instances encountered at large real-world carriers operating large hub-and-spoke service networks.

ALGO: Plenary Speaker (Wednesday, Sept. 9, 17:00-18:00, Chair Jens Stoye)
From Integer Programming to SAT-Solving in Computational Biology [click for live event]
Dan Gusfield, University of California, Davis, USA
Last year at the BCB/WABI joint conference I presented a tutorial on Integer Linear Programming (ILP) in computational biology, based on the newly published book on that topic. In writing the book, I examined more than fifty problems in computational biology where ILP has been (mostly) successful in solving realistic problem instances, and did extensive empirical investigation of many of these problems. While, the empirical results strongly support the utility of ILP in computational biology, I also ran into a few problems in computational biology where ILP was less effective than desired, or was almost totally ineffective. So, in the last year, along with two students, I have tried to see if these hard problems could be more effectively solved using approaches based on SATISFIABILITY and SAT-solving. This approach creates Boolean formulas in Conjunctive Normal Form (CNF) that express the requirements of problem instances, along with optimization targets, and then run a SAT-solver to see if these CNF formulas can be satisfied. This approach is not well-investigated in computational biology, currently discussed in only a small number of papers in the computational biology literature. I expected that the SAT approach would do no better than ILP did on these hard problems, but was very surprised that the situation (although somewhat nuanced) is mostly the opposite: SAT-solving often works very well, and so provides another powerful tool that should be explored and exploited in computational biology. In this talk, I will describe the SAT-solving approach; how we did it; what we learned; how I tried to maintain my sanity while doing it; strange observations we saw; and also give some (hopefully correct) advice on how to start working in this area. I will focus on three specific problems: Protein folding under the HP model; Gene Sorting by Reversals; and Building Optimal Phylogenetic Networks to represent clusters and trees. Much of this work was joint with Hannah Brown, and some with Lei Zuo, supported by NSF grant 1528234 and REU supplement.

ALGO: Plenary Speaker (Thursday, Sept. 10, 13:30-14:30, Chair Alfredo Navarra)
Local Distributed Certification of Global States [click for live event]
Pierre Fraigniaud, IRIF, Université Paris-Diderot, France
This talk will present some of the most recent results about the design of techniques for locally certifying the legality of a global state of a distributed system with respect to a given predicate. The talk will also discuss the connections between these techniques and fault-tolerant distributed computing. Classical techniques involve the assignment of certificates to the nodes, which are supposed to form a global proof that the system satisfies the predicate, and which can be verified locally (nodes interact with their neighbors only). More recent techniques are based on interactive proofs, i.e., they involve interactions with an external party, motivated by the development of cloud computing.

ALGO: Plenary Speaker (Thursday, Sept. 10, 17:00-18:00, Chair Christos Kaklamanis)
Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators [click for live event]
Clifford Stein, Columbia University, USA
Although sequential algorithms with (nearly) optimal running time for finding shortest paths in undirected graphs with non-negative edge weights have been known for several decades, near-optimal parallel algorithms have turned out to be a much tougher challenge. In this talk, we present a (1+epsilon)-approximate parallel algorithm for computing shortest paths in undirected graphs, achieving polylog depth and near-linear work. All prior all prior (1+epsilon)-algorithms with polylog depth perform at least superlinear work. Improving this long-standing upper bound obtained by Cohen (STOC'94) has been open for 25 years. Our algorithm uses several new tools. Prior work uses hopsets to introduce shortcuts in the graph. We introduce a new notion that we call low hop emulators. We also introduce compressible preconditioners, which we use in conjunction with Serman's framework (SODA '17) for the uncapacitated minimum cost flow problem. Join work with Alex Andoni and Peilin Zhong.

ALGOSENSORS 2020

International Symposium on Algorithms and Experiments for Wireless Sensor Networks, Sept. 9-10, 2020. Chairs: Amitabha Bagchi, Alfredo Navarra, Maria Cristina Pinotti.


Location: MS Teams "ALGOSENSORS Room". Please read [the instructions in this link] to get a better experience with the virtual conferences in ALGO 2020. Unsure about Italy time zone? [Please check here].


[Click here for the abstracts of the talks]


ALGOSENSORS: Session 1, Sept. 9, 14:00 - 15:30, Chair Christian Scheideler
Video Distributed Localization of Wireless Sensor Network Using Communication Wheel Kaustav Bose, Manash Kumar Kundu, Ranendu Adhikary, Buddhadeb Sau
Video Covering Users by a Connected Swarm Efficiently Kiril Danilchenko, Michael Segal, Zeev Nutov
Video Minimizing Total Interference in Asymmetric Sensor Networks A. Karim Abu-Affash, Paz Carmi, Matthew Katz

ALGOSENSORS: Session 2, Sept. 9, 15:30 - 16:30, Chair Giuseppe Prencipe
Video Connected Reconfiguration of Lattice-Based Cellular Structures by Finite-Memory Robots Sándor Fekete, Eike Niehs, Christian Scheffer, Arne Schmidt
Video Fast Byzantine Gathering with Visibility in Graphs Avery Miller, Ullash Saha

ALGOSENSORS: Session 3, Sept. 10, 12:00 - 13:30, Chair Mattia D'Emidio
Video Asynchronous Filling by Myopic Luminous Robots Tamas Lukovszki, Attila Hideg
Video Live Exploration with Mobile Robots in a Dynamic Ring Subhrangsu Mandal, Anisur Rahaman Molla, William K. Moses Jr.
Video Conic Formation in Presence of Faulty Robots Debasish Pattanayak, Klaus-Tycho Förster, Partha Sarathi Mandal, Stefan Schmid

ALGOSENSORS: Session 4, Sept. 10, 14:30 - 15:30, Chair Amitabha Bagchi
Video Efficient Dispersion on an Anonymous Ring in the Presence of Weak Byzantine Robots Anisur Rahaman Molla, Kaushik Mondal, William K. Moses Jr.
Video VectorTSP: A Traveling Salesperson Problem with Racetrack-like Acceleration Constraints Arnaud Casteigts, Mathieu Raffinot, Jason Schoeters

ALGOSENSORS: Session 5, Sept. 10, 15:30 - 16:30, Chair Cristina M. Pinotti
Video On Efficient Connectivity-Preserving Transformations in a Grid Abdullah Almethen, Othon Michail, Igor Potapov
Video Weighted Group Search on a Line Konstantinos Georgiou, Jesse Lucier

ATMOS 2020

International Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, Sept. 7-8, 2020. Chairs: Dennis Huisman, Christos Zaroliagis.


Location: MS Teams "ATMOS Room". Please read [the instructions in this link] to get a better experience with the virtual conferences in ALGO 2020. Unsure about Italy time zone? [Please check here].


[Click here for the abstracts of the talks]


ATMOS: Invited Speaker, Sept. 7, 18:00 - 18:30, Chair Christos Zaroliagis
Considering Multiple Preferences in Searching Multimodal Travel Itineraries
Thomas Horstmannshoff, Management Science Group, Otto von Guericke University Magdeburg, Germany
Multimodal routing apps like Google Maps are becoming increasingly popular as several new innovative transportation services have increased the possibilities to organize door-to-door mobility. Travelers expect a set of multimodal itineraries according to their individual preferences. While there are efficient approaches for finding multimodal shortest paths, the full Pareto-Front of non-dominated multimodal travel itineraries cannot be determined efficiently when more complex traveler preferences and multiple modes of transportation are considered in a large network. In this work, we propose a framework for finding a set of multimodal travel itineraries. The core idea is to use solution space sampling to determine Pareto-optimal itineraries. We especially focus on the scalability of our framework when integrating multiple traveler preferences and several mobility services in a large multimodal network. The proposed approach is evaluated with real-data of mobility services analyzing long-distance trips between major cities in Germany, taking up to five traveler preferences into account. In addition, we examine the impact of several sampling parameters as e.g. the sampling density. Joint work with Jan Fabian Ehmke, Department of Business Decision and Analytics, University of Vienna, Austria.

ATMOS: Best Paper, Sept. 7, 18:30 - 19:00, Chair Christos Zaroliagis
Video Determining All Integer Vertices of the PESP Polytope by Flipping Arcs Niels Lindner, Christian Liebchen

ATMOS: Session 1, Sept. 7, 11:45 - 12:45, Chair Dennis Huisman
Video Cheapest Paths in Public Transport: Properties and Algorithms Anita Schöbel, Reena Urban
Video On the Multi-Kind BahnCard Problem Sabine Storandt, Mike Timm

ATMOS: Session 2, Sept. 7, 13:00 - 14:00, Chair Christos Zaroliagis
Video An Efficient Solution for One-to-Many Multi-Modal Journey Planning Jonas Sauer, Dorothea Wagner, Tobias Zündorf
Video Probabilistic Simulation of a Railway Timetable Rebecca Haehn, Erika Abraham, Nils Nießen

ATMOS: Session 3, Sept. 7, 14:00 - 15:30, Chair Dennis Huisman
Video Time-Dependent Alternative Route Planning Spyros Kontogiannis, Andreas Paraskevopoulos, Christos Zaroliagis
Video Integrating ULTRA and Trip-Based Routing Jonas Sauer, Dorothea Wagner, Tobias Zündorf
Video Framing Algorithms for Approximate Multicriteria Shortest Paths Nicolas Hanusse, David Ilcinkas, Antonin Lentz

ATMOS: Session 4, Sept. 7, 15:30 - 16:30, Chair Christos Zaroliagis
Video A Rolling Horizon Heuristic with Optimality Guarantee For an On-Demand Vehicle Scheduling Problem Johann Hartleb, Marie Schmidt
Video A New Sequential Approach to Periodic Vehicle Scheduling and Timetabling Paul Bouman, Alexander Schiewe, Philine Schiewe

ATMOS: Session 5, Sept. 8, 12:00 - 13:00, Chair Christos Zaroliagis
Video Analyzing a Family of Formulations for Cyclic Crew Rostering Thomas Breugem, Twan Dollevoet, Dennis Huisman
Video Personnel Scheduling on Railway Yards Roel van den Broek, Marjan van den Akker, Han Hoogeveen

ATMOS: Session 6, Sept. 8, 14:00 - 15:30, Chair Christos Zaroliagis
Video Faster Preprocessing for the Trip-Based Public Transit Routing Algorithm Vassilissa Lehoux-Lebacque, Christelle Loiodice
Video Customizable Contraction Hierarchies with Turn Costs Valentin Buchhold, Dorothea Wagner, Tim Zeitz, Michael Zündorf
Video A Strategic Routing Framework and Algorithms for Computing Alternative Paths Thomas Bläsius, Maximilian Böther, Philipp Fischbeck, Tobias Friedrich, Alina Gries, Falk Hüffner, Otto Kißig, Pascal Lenzner, Louise Molitor, Leon Schiller, Armin Wells, Simon Wietheger

ATMOS: Session 7, Sept. 8, 15:30 - 16:30, Chair Dennis Huisman
Video Time-Dependent Tourist Tour Planning with Adjustable Profits Felix Gündling, Tim Witzel
Video Crowdsourced Delivery with Drones in Last Mile Logistics Mehdi Behroozi, Dinghao Ma

ESA 2020

European Symposium on Algorithms, Sept. 7-9, 2020. Chairs: Fabrizio Grandoni (track A), Peter Sanders (track B).


Please read [the instructions in this link] to get a better experience with the virtual conferences in ALGO 2020. Unsure about Italy time zone? [Please check here].


ESA: Test-of-Time Award 2019 (location: MS Teams "ESA Awards Room"), Tuesday, Sept. 8, 17:00 - 18: 00, Chair Hannah Blast
LINK Slides Delta-Stepping: A Parallel Single Source Shortest Path Algorithm Ulrich Meyer, Peter Sanders

ESA: Best Papers (location: MS Teams "ESA Awards Room"), Sept. 7-9, 15:00 - 15: 30, Chairs Fabrizio Grandoni and Peter Sanders
Video Slides DOI Improved Prophet Inequalities for Combinatorial Welfare Maximization with (Approximately) Subadditive Agents (best student paper track A) Hanrui Zhang
Video Slides DOI Generalizing CGAL Periodic Delaunay Triangulations (best paper track B) Georg Osang, Mael Rouxel-Labbé, Monique Teillaud
Video Slides DOI Approximate $CVP_{\infty}$ in time $2^{0.802 n}$ (best paper track A) Moritz Venzin, Friedrich Eisenbrand

IMPORTANT: Please watch videos or read the slides before ESA poster session starts.


ESA: Poster Session 1 (location: MS Teams "ESA Poster Rooms 0-9", parallel meetings), Sept. 7, 13:00-14:00
Video Slides DOI Room.0 A $(1-e^{-1}-\epsilon)$-Approximation for the Monotone Submodular Multiple Knapsack Problem Yaron Fairstein, Ariel Kulik, Joseph Seffi Naor, Danny Raz, Hadas Shachnai
Video Slides DOI Room.1 An Algorithmic Study of Fully Dynamic Independent Sets for Map Labeling Sujoy Bhore, Guangping Li, Martin Nöllenbur
Video Slides DOI Room.2 An Optimal Decentralized $(\Delta + 1)$-Coloring Algorithm Daniel Bertschinger, Johannes Lengler, Anders Martinsson, Robert Meier, Angelika Steger, Milos Trujic, Emo Welzl
Video Slides DOI Room.3 Compact Oblivious Routing in Weighted Graphs Philipp Czerner, Harald Räcke
Video Slides DOI Room.4 Finding large $H$-colorable subgraphs in hereditary graph classes Maria Chudnovsky, Jason King, Michał Pilipczuk, Paweł Rzążewski, Sophie Spirkl
Video Slides DOI Room.5 Improved Bounds for Metric Capacitated Covering Problems Sayan Bandyapadhyay
Video Slides DOI Room.6 Many visits TSP revisited Lukasz Kowalik, Shaohua Li, Wojciech Nadara, Marcin Smulewicz, Magnus Wahlström
Video Slides DOI Room.7 On the Approximation Ratio of the $k$-Opt and Lin-Kernighan Algorithm for Metric and Graph TSP Xianghui Zhong
Video Slides DOI Room.8 Polynomial Time Approximation Schemes for Clustering in Low Highway Dimension Graphs Andreas Emil Feldmann, David Saulpic
Video Slides DOI Room.9 Reconfiguration of Spanning Trees with Many or Few Leaves Nicolas Bousquet, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki, Kunihiro Wasa

IMPORTANT: Please watch videos or read the slides before ESA poster session starts.


ESA: Poster Session 2 (location: MS Teams "ESA Poster Rooms 0-9", parallel meetings), Sept. 7, 14:00-15:00
Video Slides DOI Room.0 A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time Zachary Friggstad, Chaitanya Swamy
Video Slides DOI Room.1 An Efficient, Practical Algorithm and Implementation for Computing Multiplicatively Weighted Voronoi Diagrams Martin Held, Stefan de Lorenzo
Video Slides DOI Room.2 Analysis of the Period Recovery Error Bound Amihood Amir, Itai Boneh, Michael Itzhaki, Eitan Kondratovsky
Video Slides DOI Room.3 Coresets for the Nearest-Neighbor Rule Alejandro Flores-Velazco, David Mount
Video Slides DOI Room.4 First-Order Model-Checking in Random Graphs and Complex Networks Jan Dreier, Philipp Kuinke, Peter Rossmanith
Video Slides DOI Room.5 Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time Hanlin Ren
Video Slides DOI Room.6 Mincut Sensitivity Data Structures for the Insertion of an Edge Surender Baswana, Till Knollmann, Shiv Gupta
Video Slides DOI Room.7 On the Complexity of Recovering Incidence Matrices Ramanujan M. Sridharan, Pranabendu Misra, Petr Golovach, Fedor Fomin
Video Slides DOI Room.8 The Maximum Binary Tree Problem Karthekeyan Chandrasekaran, Elena Grigorescu, Gabriel Istrate, Shubhang Kulkarni, Young-San Lin, Minshen Zhu
Video Slides DOI Room.9 The Minimization of Random Hypergraphs Thomas Bläsius, Tobias Friedrich, Martin Schirneck

IMPORTANT: Please watch videos or read the slides before ESA poster session starts.


ESA: Poster Session 3 (location: MS Teams "ESA Poster Rooms 0-9", parallel meetings), Sept. 7, 15:30-16:30
Video Slides DOI Room.0 A linear fixed parameter tractable algorithm for connected pathwidth Mamadou Moustapha Kanté, Christophe Paul, Dimitrios Thilikos
Video Slides DOI Room.1 Approximate Turing Kernelization for Problems Parameterized by Treewidth Eva-Maria Hols, Stefan Kratsch, Astrid Pieterse
Video Slides DOI Room.2 Approximation of the Diagonal of a Laplacian's Pseudoinverse for Complex Network Analysis Eugenio Angriman, Alexander van der Grinten, Maria Predari, Henning Meyerhenke
Video Slides DOI Room.3 Cutting Polygons into Small Pieces with Chords: Laser-Based Localization Esther Arkin, Rathish Das, Jie Gao, Mayank Goswami, Joseph Mitchell, Valentin Polishchuk, Csaba Toth
Video Slides DOI Room.4 Fine-Grained Complexity of Regular Expression Pattern Matching and Membership Philipp Schepper
Video Slides DOI Room.5 Kernelization of Whitney Switches Fedor Fomin, Petr Golovach
Video Slides DOI Room.6 Minimum Neighboring Degree Realization in Graphs and Trees Amotz Bar-Noy, Keerti Choudhary, Avi Cohen, David Peleg, Dror Rawitz
Video Slides DOI Room.7 On the Computational Complexity of Linear Discrepancy Lily Li, Aleksandar Nikolov
Video Slides DOI Room.8 Set Cover with Delay - Clairvoyance is not Required Yossi Azar, Ashish Chiplunkar, Shay Kutten, Noam Touitou
Video Slides DOI Room.9 The number of repetitions in 2D-strings Panagiotis Charalampopoulos, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen, Wiktor Zuba

IMPORTANT: Please watch videos or read the slides before ESA poster session starts.


ESA: Poster Session 4 (location: MS Teams "ESA Poster Rooms 0-9", parallel meetings), Sept. 8, 14:00-15:00
Video Slides DOI Room.0 A Polynomial Kernel for Line Graph Deletion Eduard Eiben, William Lochet
Video Slides DOI Room.1 Approximating k-connected m-dominating sets Zeev Nutov
Video Slides DOI Room.2 Distance bounds for high dimensional consistent digital rays and 2-D partially-consistent digital rays Man Kwun Chiu, Matias Korman, Martin Suderland, Takeshi Tokuyama
Video Slides DOI Room.3 Dynamic Matching Algorithms in Practice Monika Henzinger, Shahbaz Khan, Richard Paul, Christian Schulz
Video Slides DOI Room.4 Full complexity classification of the list homomorphism problem for bounded-treewidth graphs Karolina Okrasa, Marta Piecyk, Paweł Rzążewski
Video Slides DOI Room.5 Light Euclidean Spanners with Steiner Points Hung Le, Shay Solomon
Video Slides DOI Room.6 More on Change-Making and Related Problems Timothy M. Chan, Qizheng He
Video Slides DOI Room.7 On the Complexity of BWT-runs Minimization via Alphabet Reordering Jason Bentley, Daniel Gibney, Sharma V. Thankachan
Video Slides DOI Room.8 Optimal Polynomial-time Compression for Boolean Max CSP Bart Jansen, Michal Wlodarczyk
Video Slides DOI Room.9 Tight Approximation Algorithms for p-Mean Welfare Under Subadditive Valuations Siddharth Barman, Umang Bhaskar, Anand Krishna, Ranjani Sundaram

IMPORTANT: Please watch videos or read the slides before ESA poster session starts.


ESA: Poster Session 5 (location: MS Teams "ESA Poster Rooms 0-9", parallel meetings), Sept. 8, 15:30-16:30
Video Slides DOI Room.0 A Sub-linear Time Framework for Geometric Optimization with Outliers in High Dimensions Hu Ding
Video Slides DOI Room.1 Approximation Algorithms for Clustering with Dynamic Points Shichuan Deng, Jian Li, Yuval Rabani
Video Slides DOI Room.2 Dual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral Flow Naveen Garg, Nikhil Kumar
Video Slides DOI Room.3 Engineering fast almost optimal algorithms for bipartite graph matching Ioannis Panagiotas, Bora Uçar
Video Slides DOI Room.4 Incompressibility of H-free edge modification problems: Towards a dichotomy Dániel Marx, R. B. Sandeep
Video Slides DOI Room.5 Linear Expected Complexity for Directional and Multiplicative Voronoi Diagrams Chenglin Fan, Benjamin Raichel
Video Slides DOI Room.6 New Binary Search Tree Bounds via Geometric Inversions Parinya Chalermsook, Wanchote Jiamjitrak
Video Slides DOI Room.7 Settling the Relationship Between Wilber's Bounds for Dynamic Optimality Victor Lecomte, Omri Weinstein
Video Slides DOI Room.8 Practical Performance of Space Efficient Data Structures for Longest Common Extensions Patrick Dinklage, Johannes Fischer, Alexander Herlez, Tomasz Kociumaka, Florian Kurpicz
Video Slides DOI Room.9 Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs Panagiotis Charalampopoulos, Adam Karczmarz

IMPORTANT: Please watch videos or read the slides before ESA poster session starts.


ESA: Poster Session 6 (location: MS Teams "ESA Poster Rooms 0-9", parallel meetings), Sept. 9, 13:00-14:00
Video Slides DOI Room.0 Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free Graphs Jan Bok, Nikola Jedličková, Barnaby Martin, Daniel Paulusma, Siani Smith
Video Slides DOI Room.1 Augmenting the Algebraic Connectivity of Graphs Bogdan Manghiuc, Pan Peng, He Sun
Video Slides DOI Room.2 Efficient Computation of 2-Covers of a String Jakub Radoszewski, Juliusz Straszyński
Video Slides DOI Room.3 Finding All Global Minimum Cuts In Practice Monika Henzinger, Alexander Noe, Christian Schulz, Darren Strash
Video Slides DOI Room.4 Grundy Distinguishes Treewidth from Pathwidth Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi
Video Slides DOI Room.5 Linear Time LexDFS on Chordal Graphs Jesse Beisegel, Ekkehard Köhler, Robert Scheffler, Martin Strehler
Video Slides DOI Room.6 New Bounds on Augmenting Steps of Block-structured Integer Programs Lin Chen, Martin Koutecky, Lei Xu, Weidong Shi
Video Slides DOI Room.7 Optimally handling commitment issues in online throughput maximization Franziska Eberle, Nicole Megow, Kevin Schewior
Video Slides DOI Room.8 Reconstructing Biological and Digital Phylogenetic Trees in Parallel Ramtin Afshar, Pedro Matias, Michael Goodrich, Martha Osegueda
Video Slides DOI Room.9 Sometimes Reliable Spanners of Almost Linear Size Kevin Buchin, Sariel Har-Peled, Dániel Oláh

IMPORTANT: Please watch videos or read the slides before ESA poster session starts.


ESA: Poster Session 7 (location: MS Teams "ESA Poster Rooms 0-9", parallel meetings), Sept. 9, 14:00-15:00
Video Slides DOI Room.0 An Algorithmic Meta-Theorem for Graph Modification to Planarity and FOL Fedor Fomin, Petr Golovach, Giannos Stamoulis, Dimitrios Thilikos
Video Slides DOI Room.1 Capacitated Sum-of-Radii Clustering: An FPT Approximation Tanmay Inamdar, Kasturi Varadarajan
Video Slides DOI Room.2 Exploiting c-Closure in Kernelization Algorithms for Graph Problems Tomohiro Koana, Christian Komusiewicz, Frank Sommer
Video Slides DOI Room.3 Improved Algorithms for Alternating Matrix Space Isometry: from Theory to Practice Peter A. Brooksbank, Yinan Li, Youming Qiao, James B. Wilson
Video Slides DOI Room.4 Lower Bounds and Approximation Algorithms for Search Space Sizes in Contraction Hierarchies Johannes Blum, Sabine Storandt
Video Slides DOI Room.5 Noisy, Greedy and Not So Greedy k-means++ Anup Bhattacharya, Jan Eube, Heiko Röglin, Melanie Schmidt
Video Slides DOI Room.6 Parallel Batch-dynamic Trees via Change Propagation Umut Acar, Daniel Anderson, Guy Blelloch, Laxman Dhulipala, Sam Westrick
Video Slides DOI Room.7 Simulating Population Protocols in Sub-Constant Time per Interaction Petra Berenbrink, David Hammer, Dominik Kaaser, Ulrich Meyer, Manuel Penschuck, Hung Tran
Video Slides DOI Room.8 Space-efficient, Fast and Exact Routing in Time-dependent Road Networks Ben Strasser, Dorothea Wagner, Tim Zeitz
Video Slides DOI Room.9 The Fine-grained Complexity of Median and Center String Problems under Edit Distance Gary Hoppenworth, Jason Bentley, Daniel Gibney, Sharma V. Thankachan

IMPORTANT: Please watch videos or read the slides before ESA poster session starts.


ESA: Poster Session 8 (location: MS Teams "ESA Poster Rooms 0-9", parallel meetings), Sept. 9, 15:30-16:30
Video Slides DOI Room.0 An algorithmic weakening of the Erdős-Hajnal conjecture Édouard Bonnet, Stéphan Thomassé, Xuan Thang Tran, Rémi Watrigant
Video Slides DOI Room.1 Chordless Cycle Packing is Fixed-Parameter Tractable Dániel Marx
Video Slides DOI Room.2 Fast Preprocessing for Optimal Orthogonal Range Reporting and Range Successor with Applications to Text Indexing Younan Gao, Meng He, Yakov Nekritch
Video Slides DOI Room.3 Kruskal-based approximation algorithm for the multi-level Steiner tree problem Reyan Ahmed, Faryad Darabi Sahneh, Keaton Hamm, Stephen Kobourov, Richard Spence
Video Slides DOI Room.4 Improved Approximation Algorithm for Set Multicover with Non-Piercing Regions Rajiv Raman, Saurabh Ray
Video Slides DOI Room.5 Fully-Dynamic Coresets Monika Henzinger, Sagar Kale
Video Slides DOI Room.6 On Compact RAC Drawings Henry Förster, Michael Kaufmann
Video Slides DOI Room.7 Planar Bichromatic Bottleneck Spanning Trees A. Karim Abu-Affash, Sujoy Bhore, Paz Carmi, Joseph Mitchell
Video Slides DOI Room.8 Subexponential parameterized algorithms and kernelization on almost chordal graphs Fedor Fomin, Petr Golovach
Video Slides DOI Room.9 When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance under Translation Karl Bringmann, Marvin Künnemann, André Nusser

WABI 2020

Workshop on Algorithms in BIoinformatics, Sept. 7-9, 2020. Chairs: Carl Kingsford, Nadia Pisanti.


Location: MS Teams "WABI Room". Please read [the instructions in this link] to get a better experience with the virtual conferences in ALGO 2020. Unsure about Italy time zone? [Please check here].


WABI: Invited Speaker (Monday, Sept. 7, 16:00 – 16:30, Chair Nadia Pisanti)
The Pluralistic Promise of Pangenome Graphs
Erik Garrison, University of California Santa Cruz, USA
In the past decade a large fraction of genomic analysis has been driven by resequencing, wherein a genome is reconstructed from short reads using a reference genome as a guide. Technological advancement suggests that this situation is unlikely to continue forever. Where short second-generation sequencing reads made genome reconstruction difficult, long and increasingly-accurate third-generation sequencing allows us to make near-perfect genome assemblies with minimal effort. This progression implies that in the future, assemblies will be plentiful. But, we lack the complement to this abundance: efficient tools capable of supporting precise comparative genomics at the scale of thousands or millions of genomes. A new class of approach based on pangenomic sequence graphs attempts to meet this challenge by building complete, lossless models of populations of genomes and their relationships. These graphical pangenomes provide a basis for analyses that avoid distortion caused by reference bias. They simplify the comparison of genomes and their differences without limitation to a particular type or scale of variation. We review algorithms and results from this developing research focus, including those related to alignment, variant calling, genome assembly, and comparative genomics.

WABI: Invited Speaker (Tuesday, Sept. 8, 16:00 – 16:30, Chair Carl Kingsford)
Machine learning approaches for cancer survival prediction
Valentina Boeva, ETH Zurich, Switzerland, and Institute Cochin Paris, France.
Survival analysis in cancer represents a classic example of application of supervised methods of machine learning to biomedical research. The general aim is to predict clinical outcome of cancer patients based on molecular and clinical data. In my talk, I will present our recent work on integrating biological prior information to increase the model accuracy and stability. I will discuss our recent model for multitask learning on cancer transcriptomics data. Moreover, I will demonstrate a simple solution for the integration of biological knowledge on cancer-related signaling pathways allowing us to drastically reduce the dimensionality of input data without compromising model accuracy.

WABI: Session 1, Sept. 7, 14:00 – 15:00, Chair Rayan Chikhi
Video DOI The Longest Run Subsequence Problem S.Schrinner, M.Goel, M.Wulfert, P.Spohr, K.Schneeberger, G.W. Klau
Video DOI Sequence Searching Allowing for Non-Overlapping Adjacent Unbalanced Translocations S.Faro, D.Cantone, A.Pavone

WABI: Session 2, Sept. 7, 15:00 – 16:00, Chair Solon Pissis
Video DOI Near-Linear Time Edit Distance for Indel Channels A.Ganesh, A.Sy
Video DOI Disk Compression of k-Mer Sets Amatur Rahman, Rayan Chikhi, Paul Medvedev

WABI: Session 3, Sept. 7, 18:00 – 19:00, Chair Veli Mäkinen
Video DOI Fold Family-Regularized Bayesian Optimization for Directed Protein Evolution Trevor Frisby, Christopher Langmead
Video DOI Exact Transcript Quantification over Splice Graph Cong Ma, Hongyu Zheng, Carl Kingsford

WABI: Session 4, Sept. 8, 14:00 – 15:00, Chair Ania Gambin
Video DOI Natural Family-Free Genomic Distance Diego P. Rubert, Fábio V. Martinez, Marília D. V. Braga
Video DOI The Bourque Distances for Mutation Trees of Cancers Katharina Jahn, Niko Beerenwinkel, Louxin Zhang

WABI: Session 5, Sept. 8, 15:00 – 16:00, Chair Christina Boucher
Video DOI Economic Genome Assembly from Low Coverage Illumina and Nanopore Data Thomas Gatter, Sarah von Löhneysen, Polina Drozdova, Tom Hartmann, Peter F. Stadler
Video DOI Fast and Efficient Rmap Assembly using the Bi-labelled de Bruijn Graph Kingshuk Mukherjee, Massimiliano Rossi, Leena Salmela, Christina Boucher

WABI: Session 6, Sept. 8, 17:00 – 18:00, Chair Guillaume Marcais
Video DOI Linear Time Construction of Indexable Founder Block Graphs Veli Mäkinen, Bastien Cazaux, Massimo Equi, Tuukka Norri, Alexandru I. Tomescu
Video DOI A Graph-Theoretic Barcode Ordering Model for Linked-Reads Title Yoann Dufresne, Chen Sun, Pierre Marijon, Dominique Lavenier, Cedric Chauve, Rayan Chikhi

WABI: Session 7, Sept. 8, 18:00 – 19:00, Chair Nadia El-Mabrouk
Video DOI Advancing Divide-and-Conquer Phylogeny Estimation using Robinson-Foulds Supertrees Xilin Yu, Thien Le, Sarah Christensen, Erin Molloy, Tandy Warnow
Video DOI Phyolin: Identifying a Linear Perfect Phylogeny in Single-cell DNA Sequencing Data of Tumors Leah Weber, Mohammed El-Kebir

WABI: Session 8, Sept. 9, 14:00 – 15:30, Chair Gunnar Klau
Video DOI Fast Lightweight Accurate Xenograft Sorting Jens Zentgraf, Sven Rahmann
Video DOI Shape decomposition algorithms for laser capture microdissection Leonie Selbach, Tobias Kowalski, Klaus Gerwert, Maike Buchin, Axel Mosig
Video DOI An Interpretable Classification Method for Predicting Drug Resistance in M. Tuberculosis Hooman Zabeti, Amir Hosein Safari, Nick Dexter, Nafiseh Sedaghat, Maxwell Libbrecht, Leonid Chindelevitch

WABI: Session 9, Sept. 9, 15:30 – 16:30, Chair Tomas Vinar
Video DOI GraphBin2: Refined and Overlapped Binning of Metagenomic Contigs Using Assembly Graphs Vijini Mallawaarachchi, Anuradha Wickramarachchi, Yu Lin
Video DOI Approximate Search for Known Gene Clusters in New Genomes Using PQ-Trees title Galia R. Zimerman, Dina Svetlitsky, Meirav Zehavi, Michal Ziv-Ukelson

WAOA 2020

Workshop on Approximation and Online Algorithms, Sept. 9-10, 2020. Chairs: Christos Kaklamanis, Asaf Levin.


Location: MS Teams "WAOA Room". Please read [the instructions in this link] to get a better experience with the virtual conferences in ALGO 2020. Unsure about Italy time zone? [Please check here].


WAOA: Session 1, Sept. 9, 12:00 - 13:00, Chair Asaf Levin
Video Concave connection cost Facility Location and the Star Inventory Routing Problem Mateusz Lewandowski, Jaroslaw Byrka
Video 2-Node-Connectivity Network Design Zeev Nutov

WAOA: Session 2, Sept. 9, 13:00 - 14:00, Chair Archontia Giannopoulou
Video LP-based algorithms for multistage minimization problems Evripidis Bampis, Bruno Escoffier, Alexander Kononov
Video Maximum Coverage with Cluster Constraints: An LP-Based Approximation Technique Guido Schaefer, Bernard Zweers

WAOA: Session 3, Sept. 9, 14:00 - 15:30, Chair Antonios Antoniadis
Video Explorable Uncertainty in Scheduling with Non-Uniform Testing Times Susanne Albers, Alexander Eckl
Video A Faster FPTAS for Knapsack Problem With Cardinality Constraint Wenxin Li, Joohyun Lee, Ness Shroff
Video Memoryless Algorithms for the Generalized k-Server Problem on Uniform Metrics Dimitris Christou, Dimitris Fotakis, Grigorios Koumoutsos

WAOA: Session 4, Sept. 9, 15:30 - 16:30, Chair Pavel Vesely
Video Distributed Algorithms for Matching in Hypergraphs Oussama Hanguir, Clifford Stein
Video Online Coloring and a New Type of Adversary for Online Graph Problems Yaqiao Li, Vishnu Narayan, Denis Pankratov

WAOA: Session 5, Sept. 10, 12:30 - 13:30, Chair Zeev Nutov
Video A Constant-Factor Approximation Algorithm for Vertex Guarding a WV-Polygon Stav Ashur, Omrit Filtser, Matthew Katz
Video A Constant-Factor Approximation Algorithm for Red-Blue Set Cover with Unit Disks Raghunath Reddy Madireddy, Apurva Mudgal

WAOA: Session 6, Sept. 10, 14:30 - 15:30, Chair José Verschae
Video Lasserre Integrality Gaps for Graph Spanners and Related Problems Michael Dinitz, Yasamin Nazari, Zeyu Zhang
Video Tight Bounds on Subexponential Time Approximation of Set Cover and Related Problems Marek Cygan, Magnús M. Halldórsson, Guy Kortsarz

WAOA: Session 7, Sept. 10, 15:30 - 16:30, Chair Lars Rohwedder
Video To Close Is Easier Than To Open: Dual Parameterization To k-Median Jaroslaw Byrka, Szymon Dudycz, Pasin Manurangsi, Jan Marcinkowski, Michal Wlodarczyk
Video An Improved Approximation Algorithm for the Uniform Cost-Distance Steiner Tree Problem Ardalan Khazraei, Stephan Held