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