Quick link to daily schedule of ALGO 2021, please click below:  
MONDAY, Sept. 6  TUESDAY, Sept. 7  WEDNESDAY, Sept. 8  THURSDAY, Sept. 9  FRIDAY, Sept. 10 
Quick link to each conference programme of ALGO 2021, please click below:  
ALGOSENSORS  ALGOCLOUD  ATMOS  ESA (tracks A and B)  IPEC  WAOA 
Monday, September 6, 2021. Unsure about Portugal time zone? [Please check here]. 
MON. 6th  ROOM 1  ROOM 2  ROOM 3  ROOM 4 

12:30  Welcoming ESA & ALGOCLOUD (Auditorium)  
13:00  ESA Track A: Graph algorithms chair: Édouard Bonnet 
ESA Track A: Scalable algorithms chair: Benjamin Doerr 
ESA Track A: Computationally hard problems chair: Holger Dell 
ALGOCLOUD Session 1 
Michał Dębski, Marta Piecyk and Paweł Rzążewski: Faster 3coloring of smalldiameter graphs 
Claire Mathieu and Hang Zhou: A Simple Algorithm for Graph Reconstruction 
Jana Cslovjecsek, Friedrich Eisenbrand, Michał Pilipczuk, Moritz Venzin and Robert Weismantel: Efficient sequential and parallel algorithms for multistage stochastic integer programming using proximity 
Shahin Kamali and Pooya Nikbakht: On the FaultTolerant Online Bin Packing Problem 

Katarzyna Paluch and Mateusz Wasylkiewicz: Restricted tmatchings via halfedges 
Panagiotis Charalampopoulos, Tomasz Kociumaka, Solon Pissis and Jakub Radoszewski: Faster Algorithms for Longest Common Substring 
Leon Kellerhals, Malte Renken and Philipp Zschoche: Parameterized Algorithms for Diverse Multistage Problems 
Léonard Lys, Arthur Micoulet and Maria PotopButucaru. RSWAP: Relay based atomic crosschain swap protocol 

Éric Colin de Verdière and Thomas Magnard: An FPT algorithm for the embeddability of graphs into twodimensional simplicial complexes 
Krzysztof Potępa: Faster Deterministic Modular Subset Sum 
Marek Cygan, Alexander Kulikov, Ivan Mihajlin, Maksim Nikolaev and Grigory Reznikov: Minimum Common String Partition: Exact Algorithms 
Matthew Connor. Brief Announcement: On the Distributed Construction of Stable Networks in Polylogarithmic Parallel Time 

14:15  break 15 min and posters session  
14:30  ESA Track A: Graph algorithms chair: Ran Duan 
ESA Track A: Optimization chair: Ilan Cohen 
ESA Track A: Orientations and representatives chair: Jakub Łącki 
ALGOCLOUD Tutorial 
Thomas Bläsius, Tobias Friedrich and Maximilian Katzmann: Efficiently Approximating Vertex Cover on ScaleFree Networks with Underlying Hyperbolic Geometry 
Lin Chen, Hossein Esfandiari, Thomas Fu, Vahab Mirrokni and Qian Yu: Feature Cross Search via Submodular Optimization 
Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul, Ely Porat and Clifford Stein: Incremental Edge Orientation in Forests 
Tutorial with Stefan Schmid: SelfAdjusting Networks: Enablers, Algorithms, Complexity 

Eden Pelleg and Stanislav Živný: Additive Sparsification of CSPs 
Yaron Fairstein, Ariel Kulik and Hadas Shachnai: Modular and Submodular Optimization with Multiple Knapsack Constraints via Fractional Grouping 
Therese Biedl, Anna Lubiw, Anurag Murty Naredla, Peter Dominik Ralbovsky and Graeme Stroud: Distant Representatives for Rectangles in the Plane 

Benoit Larose, Petar Marković, Barnaby Martin, Daniel Paulusma, Siani Smith and Stanislav Živný: QCSP on Reflexive Tournaments 
Marilena Leichter, Benjamin Moseley and Kirk Pruhs: An Efficient Reduction of a Gammoid to a Partition Matroid 
Evripidis Bampis, Christoph Dürr, Thomas Erlebach, Murilo S. de Lima, Nicole Megow and Jens Schlöter: Orienting (hyper)graphs under explorable stochastic uncertainty 

15:45  break 15 min and posters session  
16:00  Keynote ESA : AARON ROTH (Auditorium): User Friendly Power Tool for Deriving Online Learning Algorithms 

17:00  break 15 min and posters session  
17:15  ESA Best Papers Session chairs: Petra Mutzel and Rasmus Pagh 
ALGOCLOUD Tutorial  
Track A best student paper: Wojciech Nadara, Mateusz Radecki, Marcin Smulewicz and Marek Sokołowski: Determining 4edgeconnected components in linear time 
Track B best student paper: Florian Wörz and JanHendrik Lorenz: Evidence for LongTails in SLS Algorithms 
Tutorial with Amitabh Trehan: Selfhealing Distributed Algorithms 

Track A best paper: Zhiyang He, Jason Li and Magnus Wahlström: Nearlineartime, Optimal Vertex Cut Sparsifiers in Directed Acyclic Graphs 

Track B best paper: Simon D. Fink, Matthias Pfretzschner and Ignaz Rutter: Experimental Comparison of PCTrees and PQTrees 

18:30  ESA TestofTime Award: Rasmus Pagh, Flemming Friche Rodler Cuckoo Hashing 
end of the day  
18:55  end of the day 
Tuesday, September 7, 2021.Unsure about Portugal time zone? [Please check here]. 
TUE. 7th  ROOM 1  ROOM 2  ROOM 3  ROOM 4 

13:00  ESA Track B: Graphs chair: Andrea Marino 
ESA Track A: Spaceefficient data structures chair: Rasmus Pagh 
ESA Track A: Parameterized algorithms chair: Akanksha Agrawal 
ALGOCLOUD Keynote 
Saman Ahmadi, Guido Tack, Daniel Harabor and Philip Kilby: Biobjective Search with Bidirectional A* 
Moses Ganardi: Compression by Contracting StraightLine Programs 
Katrin Casel, Tobias Friedrich, Davis Issac, Aikaterini Niklanovits and Ziena Zeif: Balanced Crown Decomposition for Connectivity Constraints 
CHRISTIAN SCHEIDELER :
CloudAssisted PeertoPeer Systems 

Thomas Bläsius, Tobias Friedrich and Christopher Weyand: Efficiently Computing Maximum Flows in ScaleFree Networks 
Ian Munro, Patrick K. Nicholson, Louisa Seelbach Benkner and Sebastian Wild: Hypersuccinct Trees – New universal tree source codes for optimal compressed tree data structures and range minima 
Daniel Neuen: Isomorphism Testing Parameterized by Genus and Beyond 

Lars Gottesbüren, Tobias Heuer, Peter Sanders, Christian Schulz and Daniel Seemaier: Deep Multilevel Graph Partitioning 
Davide Bilò, Sarel Cohen, Tobias Friedrich and Martin Schirneck: NearOptimal Deterministic SingleSource Distance Sensitivity Oracles 
Radu Curticapean, Holger Dell and Thore Husfeldt: Modular counting of subgraphs: Matchings, matchingsplittable graphs, and paths 

14:15  break 15 min and posters session  
14:30  ESA Track B: Optimization chair: Petra Berenbrink 
ESA Track A: Dynamic data structures chair: Gramoz Goranci 
ESA Track A: Online algorithms chair: Pierre Fraigniaud 
ALGOCLOUD Tutorial 
Markus Anders and Pascal Schweitzer: Parallel Computation of Combinatorial Symmetries 
Sepehr Assadi and Shay Solomon: Fully Dynamic Set Cover via Hypergraph Maximal Matching: An Optimal Approximation Through a Local Approach 
Sujoy Bhore and Csaba Toth: Online Euclidean Spanners 
Tutorial with Maria PotopButucaru: Gaming the Decentralized Finance 

Kolja Junginger, Ioannis Mantas, Evanthia Papadopoulou, Martin Suderland and Chee Yap: Certified Approximation Algorithms for the Fermat Point and nEllipses 
Hendrik Fichtenberger, Monika Henzinger and Wolfgang Ost: Differentially Private Algorithms for Graphs Under Continual Observation 
Nikhil Ayyadevara and Ashish Chiplunkar: The Randomized Competitive Ratio of Weighted $k$Server is at Least Exponential 

Aaron Bernstein, Aditi Dudeja and Seth Pettie: Incremental SCC Maintenance in Sparse Graphs 
Thomas Lavastida, Benjamin Moseley, R. Ravi and Chenyang Xu: Learnable and InstanceRobust Predictions for Online Matching, Flows and Load Balancing 

15:45  break 15 min and posters session  
16:00  Keynote ESA : FRAUKE LIERS (Auditorium): Network Planning and Routing Problems Over Time: Models, Complexity and Algorithms  
17:00  break 15 min and posters session  
17:15  ESA Track B: Data structures chair: Gerth Brodal 
ESA Track A: Quantum algorithms chair: Simon Apers 
ESA Track A: Game theory chair: Chaitanya Swamy 
ALGOCLOUD Session 2 
Peter Sanders, Marvin Williams and Roman Dementiev: Engineering MultiQueues: Fast Relaxed Concurrent Priority Queues 
Yassine Hamoudi: Quantum SubGaussian Mean Estimator 
Ryoga Mahara: Extension of Additive Valuations to General Valuations on the Existence of EFX 
Bugra Caskurlu, Utku Acikalin, Piotr Wojciechowski and K. Subramani. New Results on TestCost Minimization in Database Migration 

David Lee, Samuel McCauley, Shikha Singh and Max Stein. Telescoping Filter: A Practical Adaptive Filter 
Ojas Parekh and Kevin Thompson: Beating Random Assignment for Approximating Quantum 2Local Hamiltonian Problems 
Alexander Braun, Matthias Buttkus and Thomas Kesselheim: Asymptotically Optimal Welfare of Posted Pricing for Multiple Items with MHR Distributions 
Anna Katharina Hildebrandt, Ernst Althaus and Andreas Hildebrandt. Privately querying Privacy: privacy estimation with guaranteed privacy of user and database party 

18:05  break 15 min and posters session  
18:20  ESA Track B: Strings chair: Henning Meyerhenke 
ESA Track A: Geometric data structures chair: Laxman Dhulipala 
ESA Track A: Optimization chair: Omri Weinstein 
ALGOCLOUD Business meeting 
Nico Bertram, Jonas Ellert and Johannes Fischer: Lyndon Words Accelerate Suffix Sorting 
Jean Cardinal, John Iacono and Grigorios Koumoutsos: WorstCase Efficient Dynamic Geometric Independent Set 
Daniel Lokshtanov, Subhash Suri and Jie Xue: Efficient Algorithms for Least Square Piecewise Polynomial Regression 
ALGOCLOUD Business Meeting  
Dominik Kempa and Ben Langmead: Fast and SpaceEfficient Construction of AVL Grammars from the LZ77 Parsing 
Timothy M. Chan and Zhengcheng Huang: Dynamic Colored Orthogonal Range Searching 
Daniel Dadush, Zhuan Khye Koh, Bento Natura and László A. Végh: An Accelerated NewtonDinkelbach Method and its Application to Two Variables Per Inequality Systems 

Grigorios Loukides and Solon Pissis: Bidirectional String Anchors: a New String Sampling Mechanism 
Younan Gao and Meng He: Space Efficient TwoDimensional Orthogonal Colored Range Counting 
Yishu Wang, Arnaud Mary, MarieFrance Sagot and Blerina Sinaimeri: A general framework for enumerating equivalence classes of solutions 

19:35  end of the day 
Wednesday, September 8, 2021. Unsure about Portugal time zone? [Please check here]. 
WED. 8th  ROOM 1  ROOM 2  ROOM 3  ROOM 4 

12:30  Welcoming IPEC  
13:00  Keynote IPEC : FRANK STEPHAN & BAKHADYR KHOUSSAINOV (Auditorium): Parity Games  Background and Algorithms 

14:00  break 15 min and posters session  
14:15  ESA Track A: Graph algorithms chair: Christos Zaroliagis 
ESA Track A: Computational geometry chair: Jeff Phillips 
ESA Track A: Sublinear algorithms chair: Clément Canonne 
IPEC Session 1 
Zdenek Dvorak and Abhiruk Lahiri: Approximation schemes for bounded distance problems on fractionally treewidthfragile graphs 
Jean Cardinal, Justin Dallant and John Iacono: An Instanceoptimal Algorithm for Bichromatic Rectangular Visibility 
Hu Ding: Stability Yields Sublinear Time Algorithms for Geometric Optimization in Machine Learning 
Huib Donkers, Bart M. P. Jansen and Michal Wlodarczyk. Preprocessing for Outerplanar Vertex Deletion: An Elementary Kernel of Quartic Size 

Maor Akav and Liam Roditty: A unified approach for all pairs approximate shortest paths in weighted undirected graphs 
Carlos Alegría, Ioannis Mantas, Evanthia Papadopoulou, Marko Savić, Hendrik Schrezenmaier, Carlos Seara and Martin Suderland: The Voronoi Diagram of Rotating Rays with applications to Floodlight Illumination 
Mark de Berg, Morteza Monemizadeh and Yu Zhong: kCenter Clustering with Outliers in the SlidingWindow Model 
Akanksha Agrawal, Aditya Anand and Saket Saurabh. A Polynomial Kernel for deletion to Ptolemaic Graphs 

Timothy M. Chan: AllPairs Shortest Paths for RealWeighted Undirected Graphs with Small Additive Error 
Anna Lubiw and Anurag Murty Naredla: The Visibility Center of a Simple Polygon 
Sepehr Assadi, Deeparnab Chakrabarty and Sanjeev Khanna: >Graph Connectivity and Single Element Recovery via Linear and OR Queries 
Lawqueen Kanesh, Jayakrishnan Madathil, Abhishek Sahu, Saket Saurabh and Shaily Verma. A Polynomial Kernel for Bipartite Permutation Vertex Deletion 

15:30  break 15 min and posters session  
15:45  ESA Track A: Flows and cuts chair: Jason Li 
ESA Track A: Computational geometry chair: Zac Friggstad 
ESA Track A: Hardness results chair: Marvin Künnemann 
IPEC Session 2 
William Maxwell and Amir Nayyeri: Generalized maxflows and mincuts in simplicial complexes 
Sariel HarPeled and Timothy Zhou: Improved Approximation Algorithms for Tverberg Partitions 
Pavel Dvořák, Michal Koucký, Karel Král and Veronika Slívová: Data Structures Lower Bounds and Popular Conjectures 
Maël Dumas, Anthony Perez and Ioan Todinca. Polynomial kernels for strictly chordal edge modification problems 

Evangelos Kosinas, Loukas Georgiadis and Giuseppe F. Italiano: Computing the 4EdgeConnected Components of a Graph in Linear Time 
Alejandro FloresVelazco and David Mount: BoundarySensitive Approach for Approximate NearestNeighbor Classification 
David Caballero, Timothy Gomez, Robert Schweller and Tim Wylie: Covert Computation in Staged SelfAssembly: Verification is PSPACEcomplete 
Gabriel Bathie, Nicolas Bousquet and Théo Pierron. (Sub)linear kernels for edge modification problems towards structured graph classes 

Karthekeyan Chandrasekaran and Weihang Wang: ℓpnorm Multiway Cut 
Jasper C.H. Lee, Jerry Li, Christopher Musco, Jeff Phillips and Wai Ming Tai: Finding an Approximate Mode of a Kernel Density Estimate 
Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń and Wiktor Zuba: Hardness of Detecting Abelian and Additive Square Factors in Strings 
Yixin Cao and Yuping Ke. Improved Kernels for Edge Modification Problems 

17:00  break 15 min and posters session  
17:15  ESA Track A: Graph algorithms chair: Zac Friggstad 
ESA Track A: Optimization and scheduling chair: Frances Rosamond 
IPEC Session 3  
Thomas Bläsius, Simon D. Fink and Ignaz Rutter: Synchronized Planarity with Applications to Constrained Planarity Problems 
Tomas MartinezMunoz and Andreas Wiese: FPT and FPTapproximation algorithms for Unsplittable Flow on Trees 
Alejandro Grez, Filip Mazowiecki, Michał Pilipczuk, Gabriele Puppis and Cristian Riveros. Dynamic data structures for timed automata acceptance 

Boris Klemz: Convex drawings of hierarchical graphs in linear time, with applications to planar graph morphing 
Fabrizio Grandoni, Tobias Mömke and Andreas Wiese: Faster (1+epsilon)approximation for Unsplittable Flow on a Path via resource augmentation and back 
Max Bannach, Zacharias Heinrich, Ruediger Reischuk and Till Tantau. Dynamic Kernels for Hitting Sets and Set Packing 

Ramanujan M. Sridharan: On Approximate Compressions for Connected Minorhitting Sets 
Klaus Jansen and Malin Rau: Closing the gap for single resource constraint scheduling 
Vít Jelínek, Michal Opler and Jakub Pekárek. Long paths make patterncounting hard, and deep trees make it harder 

Joergen BangJensen, Kristine Vitting Klinkby and Saket Saurabh: kDistinct Branchings Admits a Polynomial Kernel 
Guillaume Sagnol and Daniel Schmidt Genannt Waldschmidt: Restricted Adaptivity in Stochastic Scheduling 
Julio Araujo, Marin Bougeret, Victor A. Campos and Ignasi Sau. A new framework for kernelization lower bounds: the case of Maximum Minimal Vertex Cover 

18:55  break 15 min and posters session  
19:10  ESA Business meeting  IPEC Award session  
20:10  end of the day 
Thursday, September 9, 2021. Unsure about Portugal time zone? [Please check here]. 
THU. 9th  ROOM 1  ROOM 2  ROOM 3  ROOM 4 

12:30  Welcoming ATMOS, WAOA and ALGOSENSORS (Auditorium)  
13:00  ALGOSENSORS Keynote : BERNHARD HAEUPLER (Auditorium): UniversallyOptimal Distributed Algorithms, (Congestion+Dilation)Competitive Oblivious Routing, and HopConstrained Network Design Session chair: Leszek Gąsieniec 

14:00  break 15 min and posters session  
14:15  ATMOS Session 1  WAOA Session 1 Session chair: Britta Peis 
ALGOSENSORS Session 1: Distributed algorithms Session chair: Thomas Erlebach 
IPEC Session 4 
Niels Lindner, Christian Liebchen and Berenike Masing: Forward Cycle Bases and Periodic Timetabling 
Waldo Gálvez, Francisco SanhuezaMatamala and José A. Soto: Approximation Algorithms for VertexConnectivity Augmentation on the Cycle 
Louis Esperet, Sébastien Julliot and Arnaud de Mesmay: Distributed coloring and the local structure of unitdisk graphs 
Laurent Bulteau, Bertrand Marchand and Yann Ponty. A new parametrization for independent set reconfiguration and applications to RNA kinetics 

Marc Goerigk, Anita Schöbel and Felix Spühler: A Phase I Simplex Method for Finding Feasible Periodic Timetables 
Václav Blažej, Pratibha Choudhary, Dušan Knop, Jan Matyáš Křišťan, Ondrej Suchy and Tomáš Valla: Constant Factor Approximation for Tracking Paths and Fault Tolerant Feedback Vertex Set 
Thorsten Götte, Christina Kolb, Christian Scheideler and Julian Werthmann: Beep And Sleep: Message and Energy Efficient SetCover 
Hans L. Bodlaender, Carla Groenland and Céline M. F. Swennenhuis. Parameterized Complexities of Dominating and Independent Set Reconfiguration 

Vera Grafe and Anita Schöbel: Solving the periodic scheduling problem: An assignment approach in nonperiodic networks 
Hao Sun: An Improved Approximation Bound for Minimum Weight Dominating Set on Graphs of Bounded Arboricity 
Mikhail Raskin: Population protocols with unreliable communication 
Andreas Emil Feldmann and Ashutosh Rai. On Extended Formulations for Parameterized Steiner Trees 

15:30  break 15 min and posters session  
15:45  ATMOS Session 2  WAOA Session 2 Session chair: Vera Traub 
ALGOSENSORS Session 2: Gathering Session chair: Tomasz Radzik 
IPEC Session 5 
Matthias MüllerHannemann, Ralf Rückert, Alexander Schiewe and Anita Schöbel: Towards Improved Robustness of Public Transport by a MachineLearned Oracle 
Szymon Dudycz, Pasin Manurangsi and Jan Marcinkowski: Tight Inapproximability of Minimum Maximal Matching on Bipartite Graphs and Related Problems 
Quentin Bramas, Anissa Lamani and Sebastien Tixeuil: Stand Up Indulgent Gathering 
Shaohua Li and Marcin Pilipczuk. Hardness of Metric Dimension in Graphs of Constant Treewidth 

SyuNing Johnn, Yiran Zhu, Andrés MiniguanoTrujillo and Akshay Gupte: Solving the Home Service Assignment, Routing, and Appointment scheduling (HSARA) problem with Uncertainties 
Toshihiro Fujito and Takumi Tatematsu: On bMatchings and bEdge Dominating Sets: A 2Approximation Algorithm for the 4Edge Dominating Set Problem 
Jannik Castenow, Jonas Harbig, Daniel Jung, Till Knollmann and Friedhelm Meyer auf der Heide: Gathering a Euclidean Closed Chain of Robots in Linear Time (best paper + best student paper) 
Guillaume Ducoffe. Maximum Matching in almost linear time on the graphs of bounded cliquewidth 

Daniela Gaul, Kathrin Klamroth and Michael Stiglmayr: Solving the Dynamic DialaRide Problem Using a RollingHorizon EventBased Graph 
Dylan Huizing and Guido Schäfer: The Traveling kMedian Problem: Approximating Optimal Network Coverage 
Guillaume Ducoffe. Optimal centrality computations within bounded cliquewidth graphs 

17:00  break 15 min and posters session  
17:15  WAOA keynote (Auditorium): DANIEL LOKSHTANOV chair: Jochen Könemann 

18:15  break 15 min and posters session  
18:30  ATMOS Session 3: chairs: Matthias MüllerHannemann and Federico Perea 
WAOA Session 3 Session chair: Hung Le 
ALGOSENSORS Business meeting Session chair: Tomasz Radzik 
IPEC business meeting 
Robert Benkoczi, Binay Bhattacharya, Yuya Higashikawa, Tsunehiko Kameda, Naoki Katoh and Junichi Teruyama: Locating Evacuation Centers Optimally in Path and Cycle Networks 
G. Jaykrishnan and Asaf Levin: EPTAS for Load Balancing Problem on Parallel Machines with a Nonrenewable Resource 
Business meeting  Business meeting  
Diptendu Chatterjee and Bimal K. Roy: An Improved Scheduling Algorithm for Traveling Tournament Problem with Maximum Trip Length Two 
Leah Epstein: Several methods of analysis for cardinality constrained bin packing 

19:20  break 10 min  end of the day  
19:30  ATMOS Business meeting and BestPaper Award 
end of the day  
20:00  end of the day 
Friday, September 10, 2021. Unsure about Portugal time zone? [Please check here]. 
FRI. 10th  ROOM 1  ROOM 2  ROOM 3  ROOM 4 

13:00  ATMOS Session 4  WAOA Session 4 Session chair: Jarek Byrka 
ALGOSENSORS Session 3: Admission control & Programmable matter Session chair: Giuseppe Antonio Di Luna 
IPEC Tutorial Session 6 
Peter Damaschke: Distancebased Solution of Patrolling Problems with Individual Waiting Times 
Ilan Cohen, Izack Cohen and Iyar Zaks: Weighted completion time minimization for capacitated parallel machines 
Assaf Rabinowitz and Dror Rawitz: Overflow Management with SelfEliminations 
Tutorial with Édouard Bonnet Twinwidth 

Marco Silva, Joao Pedro Pedroso, Ana Viana and Xenia Klimentova: A branchpriceandcut algorithm for stochastic crowd shipping lastmile delivery with correlated marginals 
Marten Maack, Friedhelm Meyer Auf der Heide and Simon Pukrop: Server Cloud Scheduling 
Abdullah Almethen, Othon Michail and Igor Potapov: Distributed Transformations of Hamiltonian Shapes based on Line Moves 

Elia Costa and Francesco Silvestri: On the Bike Spreading Problem 
B.Tauer, and L. Vargas Koch: FIFO and Randomized Competitive Packet Routing Games 
Matthew Connor, Othon Michail and Igor Potapov: Centralised ConnectivityPreserving Transformations for Programmable Matter: A Minimal Seed Approach 

14:15  break 15 min and posters session  
14:30  ATMOS Session 5  WAOA Session 5 Session chair: Andreas Feldmann 
ALGOSENSORS Session 4: Search & Evacuation Session chair: Petra Berenbrink 
IPEC Session 7 
Guvenc Sahin, Amin Ahmadi Digehsara and Ralf Borndörfer: Efficient Algorithms for the MultiPeriod Line Planning Problem in Public Transportation (short paper) 
Jeff Giliberti and Andreas Karrenbauer: Improved Online Algorithm for Fractional Knapsack in the Random Order Model 
Konstantinos Georgiou, Sean Leizerovich, Jesse Lucier and Somnath Kundu: Evacuating from ellp Unit Disks in the Wireless Model 
Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé and Rémi Watrigant. Twinwidth and polynomial kernels 

Hector Gatt, JeanMarie Freche, Fabien Lehuede and Thomas Yeung: A column generationbased heuristic for the Line Planning Problem with Service Levels (short paper) 
Yann Disser, Max Klimm and David Weckbecker: Fractionally Subadditive Maximization under an Incremental Knapsack Constraint 
Nikos Leonardos, Aris Pagourtzis and Ioannis Papaioannou: Byzantine Fault Tolerant SymmetricPersistent Circle Evacuation 
Jakub Balabán and Petr Hlineny. TwinWidth is Linear in the Poset Width 

Natividad GonzálezBlanco, Antonio J. Lozano, Juan A. Mesa and Vladimir Marianov: An integrated model for rapid and slow transit network design (short paper) 
Marcin Bienkowski, Martin Böhm, Martin Koutecký, Thomas Rothvoß, Jiří Sgall and Pavel Veselý: Improved Analysis of Online Balanced Clustering 
Dennis Fischer, Tim A. Hartmann, Stefan Lendl and Gerhard J. Woeginger. An Investigation of the Recoverable Robust Assignment Problem 

15:45  break 15 min and posters session  
16:00  ATMOS keynote : ANITA SCHÖBEL (Auditorium): Approaches for integrated planning: The case of public transport optimization 

17:00  break 15 min and posters session  
17:15  ATMOS Session 6  WAOA Session 6 Session chair: Jochen Könemann 
IPEC Session 8  
Daniel Chen, Christian Sommer and Daniel Wolleb: Fast Map Matching with VertexMonotone Fréchet Distance 
Stavros Kolliopoulos and Antonis Skarlatos: PrecedenceConstrained Covering Problems with Multiplicity Constraints 
Haozhe An, Mohit Jayanti Gurumukhani, Russell Impagliazzo, Michael Jaber, Marvin Künnemann and Maria Paula Parga Nina. The finegrained complexity of multidimensional ordering properties 

Payas Rajan, Moritz Baum, Michael Wegner, Tobias Zündorf, Christian West, Dennis Schieferdecker and Daniel Delling: Robustness Generalizations of the Shortest Feasible Path Problem for Electric Vehicles 
Nikhil Bansal and Ilan Cohen: Contention Resolution, Matrix Scaling and Fair Allocation 
Akanksha Agrawal, Ravi Kiran Allumalla and Varun Teja Dhanekula. Refuting FPT Algorithms for Some Parameterized Problems Under GapETH 

Vassilissa LehouxLebacque and Christelle Loiodice: Transfer customization with the TripBased Public Transit Routing Algorithm 
Hugo Jacob, Thomas Bellitto, Oscar Defrain and Marcin Pilipczuk. Close relatives (of Feedback Vertex Set), revisited 

18:30  break 15 min and posters session  
18:45  ATMOS Session 7 chair: Matthias MüllerHannemann 
IPEC Session 9  
Niels Lindner, Pedro Maristany de Las Casas and Philine Schiewe: Optimal Forks: Preprocessing SingleSource Shortest Path Instances with Interval Data 
Igor Razgon. Classification of OBDD size for monotone 2CNFs 

Carlo S. Sartori, Pieter Smet and Greet Vanden Berghe: Efficient durationbased workload balancing for interdependent vehicle routes 
Vikraman Arvind and Venkatesan Guruswami. CNF Satisfiability in a Subspace and Related Problems 

Elisabet Burjons and Peter Rossmanith. Lower Bounds for Conjunctive and Disjunctive Turing Kernels 

20:25  end of the day 
Thursday, September 9, 2021. Unsure about Portugal time zone? [Please check here]. 
THU. 9th  ROOM 3  

12:30  Welcoming ALGOSENSORS (Auditorium)  
13:00  ALGOSENSORS Keynote : BERNHARD HAEUPLER (Auditorium): UniversallyOptimal Distributed Algorithms, (Congestion+Dilation)Competitive Oblivious Routing, and HopConstrained Network Design 

14:00  break 15 min and posters session  
14:15  ALGOSENSORS Session 1: Distributed algorithms 

Louis Esperet, Sébastien Julliot and Arnaud de Mesmay: Distributed coloring and the local structure of unitdisk graphs 

Thorsten Götte, Christina Kolb, Christian Scheideler and Julian Werthmann: Beep And Sleep: Message and Energy Efficient SetCover 

Mikhail Raskin: Population protocols with unreliable communication 

15:30  break 15 min and posters session  
15:45  ALGOSENSORS Session 2: Gathering 

Quentin Bramas, Anissa Lamani and Sebastien Tixeuil: Stand Up Indulgent Gathering 

Jannik Castenow, Jonas Harbig, Daniel Jung, Till Knollmann and Friedhelm Meyer auf der Heide: Gathering a Euclidean Closed Chain of Robots in Linear Time (best paper + best student paper) 

17:00  break 15 min and posters session  
17:15  WAOA keynote : DANIEL LOKSHTANOV (Auditorium) "How to Navigate Through Obstacles (and How to Place Them)"  
18:15  break 15 min and posters session  
18:30  ALGOSENSORS Business meeting  
19:30  end of the day 
Friday, September 10, 2021. Unsure about Portugal time zone? [Please check here]. 
FRI. 10th  ROOM 3  

13:00  ALGOSENSORS Session 3: Admission control & Programmable matter 

Assaf Rabinowitz and Dror Rawitz: Overflow Management with SelfEliminations 

Abdullah Almethen, Othon Michail and Igor Potapov: Distributed Transformations of Hamiltonian Shapes based on Line Moves 

Matthew Connor, Othon Michail and Igor Potapov: Centralised ConnectivityPreserving Transformations for Programmable Matter: A Minimal Seed Approach 

14:15  break 15 min and posters session  
14:30  ALGOSENSORS Session 4: Search & Evacuation 

Konstantinos Georgiou, Sean Leizerovich, Jesse Lucier and Somnath Kundu: Evacuating from ellp Unit Disks in the Wireless Model 

Nikos Leonardos, Aris Pagourtzis and Ioannis Papaioannou: Byzantine Fault Tolerant SymmetricPersistent Circle Evacuation 

15:45  break 15 min and posters session  
16:00  ATMOS keynote : ANITA SCHÖBEL (Auditorium): Approaches for integrated planning: The case of public transport optimization 

17:00  end of the day 
ALGOSENSORS Keynote (Thursday, Sept. 9, 13:0014:15) 
UniversallyOptimal Distributed Algorithms, (Congestion+Dilation) Competitive Oblivious Routing, and HopConstrained Network Design 
Bernhard Haeupler, CMU, USA & ETHZ, SWITZERLAND 
Many tasks on graphs/networks are optimizing either:

ALGOSENSORS Session 1 (Thursday, Sept. 9, 14:1515:30) 
Distributed coloring and the local structure of unitdisk graphs 
Louis Esperet, Sebastien Julliot and Arnaud de Mesmay 
Coloring unitdisk graphs efficiently is an important problem in the global and distributed settings, with applications in radio channel assignment problems when the communication relies on omnidirectional antennas of the same power. In this context it is important to bound not only the complexity of the coloring algorithms, but also the number of colors used. In this paper, we consider two natural distributed settings. In the locationaware setting (when nodes know their coordinates in the plane), we give a constant time distributed algorithm coloring any unitdisk graph $G$ with at most $(3+\epsilon)\omega(G)+6$ colors, for any constant $\epsilon>0$, where $\omega(G)$ is the clique number of $G$. This improves upon a classical 3approximation algorithm for this problem, for all unitdisk graphs whose chromatic number significantly exceeds their clique number. When nodes do not know their coordinates in the plane, we give a distributed algorithm in the LOCAL model that colors every unitdisk graph $G$ with at most $5.68\omega(G)$ colors in $O(\log^3 \log n)$ rounds. Moreover, when $\omega(G)=O(1)$, the algorithm runs in $O(\log^* n)$ rounds. This algorithm is based on a study of the local structure of unitdisk graphs, which is of independent interest. We conjecture that every unitdisk graph $G$ has average degree at most $4\omega(G)$, which would imply the existence of a $O(\log n)$ round algorithm coloring any unitdisk graph $G$ with (approximatively) $4\omega(G)$ colors. 
ALGOSENSORS Session 1 (Thursday, Sept. 9, 14:1515:30) 
Beep And Sleep: Message and Energy Efficient SetCover 
Thorsten Götte, Christina Kolb, Christian Scheideler and Julian Werthmann. 
We observe message and energyefficient distributed algorithms for the \textsc{SetCover} Problem in the $KT_0$ and \textsc{Beeping} model. Given a ground set $U$ of $n$ elements and $m$ subsets of $U$, we aim to find the minimal number of these subsets that contain all elements. In the default distributed setup of this problem, each set has a bidirected communication link with each element it contains. Our first result is a $\tilde{O}(\log^2(\Delta))$time and $\tilde{O}(\sqrt{\Delta)}(n+m))$message algorithm with expected approximation ratio of $O(\log(\Delta))$ in the $KT_0$ model. The value $\Delta$ denotes the maximum of each subset's cardinality and the number of sets an element is contained in. Our algorithm is \emph{almost} optimal concerning time and message complexity. Further, we present the first \textsc{SetCover} algorithm for general instances in the \textsc{Beeping} model. It computes an $\tilde{O}(\sqrt[k]{\Delta})$approximation in time $O(k^3)$ for any parameter $k>3$. Thus, it can trade runtime for approximation ratio similar to the celebrated algorithm by Kuhn and Wattenhofer [PODC '03]. 
ALGOSENSORS Session 1 (Thursday, Sept. 9, 14:1515:30) 
Population protocols with unreliable communication 
Mikhail Raskin. 
Population protocols are a model of distributed computation intended for the study of networks of independent computing agents with dynamic communication structure. Each agent has a finite number of states, and communication occurs nondeterministically, allowing the involved agents to change their states based on each other's states. In the present paper we study unreliable models based on population protocols and their variations from the point of view of expressive power. We model the effects of message loss. We show that for a general definition of protocols with unreliable communication with constantstorage agents such protocols can only compute predicates computable by immediate observation (IO) population protocols (sometimes also called oneway protocols). Immediate observation population protocols are inherently tolerant to unreliable communication and keep their expressive power under a wide range of fairness conditions. We also prove that a large class of messagebased models that are generally more expressive than IO becomes strictly less expressive than IO in the unreliable case. 
ALGOSENSORS Session 2 (Thursday, Sept. 9, 15:4517:00) 
Stand Up Indulgent Gathering 
Quentin Bramas, Anissa Lamani and Sebastien Tixeuil. 
We consider a swarm of mobile robots evolving in a bidimensional Euclidean space. We study the stronger variant of crashtolerant gathering: if no robot crashes, robots have to meet at the same arbitrary location, not known beforehand, in finite time; if one or several robots crash at the same location, the remaining correct robots gather at the crash location to rescue them. Motivated by impossibility results in the semisynchronous setting, we present the first solution to the problem for the fully synchronous setting that operates in the vanilla LookComputeMove model with no additional hypotheses: robots are oblivious, disoriented, have no multiplicity detection capacity, and may start from arbitrary positions (including those with multiplicity points). We furthermore show that robots gather in a time that is proportional to the initial maximum distance between robots. 
ALGOSENSORS Session 2 (Thursday, Sept. 9, 15:4517:00) 
Gathering a Euclidean Closed Chain of Robots in Linear Time  (best paper + best student paper) 
Jannik Castenow, Jonas Harbig, Daniel Jung, Till Knollmann and Friedhelm Meyer Auf der Heide. 
We focus on the following question about \Gathering/ of $n$ autonomous, mobile robots in the Euclidean plane: Is it possible to solve \Gathering/ of robots that do not agree on their coordinate systems (disoriented) and see other robots only up to a constant distance (limited visibility) in linear time? Up to now, such a result is only known for robots on a twodimensional grid. We answer the question positively for robots that are connected in one closed chain, i.e., every robot is connected to exactly two other robots, and the connections form a cycle. We show that these robots can be gathered by asynchronous robots (\async{}) in $\Theta\left(n\right)$ epochs assuming the \Luminous/ model that equips the robots with locally visible lights. The lights are used to initiate and perform socalled runs along the chain, which are essential for the linear runtime. Starting of runs is done by determining locally unique robots (based on geometric shapes of neighborhoods). In contrast to the grid, this is not possible in every configuration in the Euclidean plane. Based on the theory of isogonal polygons by Gr\"unbaum, we identify the class of isogonal configurations in which, due to a high symmetry, no locally unique robots can be identified. Our solution consists of two algorithms that might be executed in parallel: The first one gathers isogonal configurations without any lights. The second one works for nonisogonal configurations; it is based on the concept of runs using a constant number of lights. 
ALGOSENSORS Session 3 (Friday, Sept. 10, 13:0014:15) 
Overflow Management with SelfEliminations 
Assaf Rabinowitz and Dror Rawitz. 
We study admission control with packet redundancy, where large data
items, called \emph{superpackets}, exceed some Maximum Transmission
Unit (MTU) and therefore are broken into several smaller packets.
It is assumed that each superpacket is comprised of $k$ packets, and that a superpacket is considered useful if at least $(1\beta)k$ of its packets arrive at the receiving end, for some \emph{redundancy} parameter $\beta \in [0,1)$. Our goal is to maximize the total profit of useful superpackets, under an overloaded network, where we are forced to drop packets. Our starting point is an algorithm, called \priority, which is based on assigning a random priority to each superpacket. This algorithm was shown to perform well when $\beta = 0$, with and without a buffer. However, the performance of \priority deteriorates with the increase of $\beta$, since it delivers too many packets for high priority superpackets. To tackle this issue, we propose an online algorithm which introduces randomized \emph{selfelimination} of packets, called \pse. When there is no buffer, we show that the competitive ratio of \pse is better than the competitive ratio of \priority, for the case where $(1\beta)^3 \cdot \rho_{\max} \geq 1$, where $\rho_{\max}$ is the maximal burst sizerouter capacity ratio. For realworld values ($\rho_{\max} \leq 1.5$), \pse outperforms \priority for $\beta \geq 0.14$. We also present simulation results, with a buffer, that demonstrate the behavior of \pse in comparison with \priority and \textsc{taildrop}. It is shown that \pse performs much better than \priority when $\beta$ is large. In fact, it is shown that \pse behaves at least as good as both algorithms. 
ALGOSENSORS Session 3 (Friday, Sept. 10, 13:0014:15) 
Distributed Transformations of Hamiltonian Shapes based on Line Moves 
Abdullah Almethen, Othon Michail and Igor Potapov. 
We consider a discrete system of $n$ simple indistinguishable devices, called \emph{agents}, forming a \emph{connected} shape $S_I$ on a twodimensional square grid. Agents are equipped with a linearstrength mechanism, called a \emph{line move}, by which an agent can push a whole line of consecutive agents in one of the four directions in a single timestep. We study the problem of transforming an initial shape $S_I$ into a given target shape $S_F$ via a finite sequence of line moves in a distributed model, where each agent can observe the states of nearby agents in a Moore neighbourhood. Our main contribution is the first distributed connectivitypreserving transformation that exploits line moves within a total of $O(n \log_2 n)$ moves, which is asymptotically equivalent to that of the bestknown centralised transformations. The algorithm solves the \emph{line formation problem} that allows agents to form a final straight line $S_L$, starting from any shape $ S_I $, whose \emph{associated graph} contains a Hamiltonian path. 
ALGOSENSORS Session 3 (Friday, Sept. 10, 13:0014:15) 
Centralised ConnectivityPreserving Transformations for Programmable Matter: A Minimal Seed Approach 
Matthew Connor, Othon Michail and Igor Potapov. 
We study a model of programmable matter systems consisting of $n$ devices lying on a 2dimensional square grid which are able to perform the minimal mechanical operation of rotating around each other. The goal is to transform an initial shape A into a target shape B. We investigate the class of shapes which can be constructed in such a scenario under the additional constraint of maintaining global connectivity at all times. We focus on the scenario of transforming nice shapes, a class of shapes consisting of a central line $L$ where for all nodes $u$ in $S$ either $u \in L$ or $u$ is connected to $L$ by a line of nodes perpendicular to $L$. We prove that by introducing a minimal 3node seed it is possible for the canonical shape of a line of $n$ nodes to be transformed into a nice shape of $n1$ nodes. We use this to show that a 4node seed enables the transformation of nice shapes of size $n$ into any other nice shape of size $n$ in $O(n^2)$ time. We leave as an open problem the expansion of the class of shapes which can be constructed using such a seed to include those derived from nice shapes. 
ALGOSENSORS Session 4 (Friday, Sept. 10, 14:3015:45) 
Evacuating from ellp Unit Disks in the Wireless Model 
Konstantinos Georgiou, Sean Leizerovich, Jesse Lucier and Somnath Kundu 
The searchtype problem of evacuating 2 robots in the wireless model from the (Euclidean) unit disk was first introduced and studied by Czyzowicz et al. [DISC'2014]. Since then, the problem has seen a long list of followup results pertaining to variations as well as to upper and lower bound improvements. All established results in the area study this 2dimensional searchtype problem in the Euclidean metric space where the search space, i.e. the unit disk, enjoys significant (metric) symmetries. We initiate and study the problem of evacuating 2 robots in the wireless model from $\ell_p$ unit disks, $p \in [1,\infty)$, where in particular robots' moves are measured in the underlying metric space. To the best of our knowledge, this is the first study of a searchtype problem with mobile agents in more general metric spaces. The problem is particularly challenging since even the circumference of the $\ell_p$ unit disks have been the subject of technical studies. In our main result, and after identifying and utilizing the very few symmetries of $\ell_p$ unit disks, we design \emph{optimal evacuation algorithms} that vary with $p$. Our main technical contributions are twofold. First, in our upper bound results, we provide (nearly) closed formulae for the worst case cost of our algorithms. Second, and most importantly, our lower bounds' arguments reduce to a novel observation in convex geometry which analyzes tradeoffs between arc and chord lengths of $\ell_p$ unit disks as the endpoints of the arcs (chords) change position around the perimeter of the disk, which we believe is interesting in its own right. Part of our argument pertaining to the latter property relies on a computer assisted numerical verification that can be done for nonextreme values of $p$. 
ALGOSENSORS Session 4 (Friday, Sept. 10, 14:3015:45) 
Byzantine Fault Tolerant SymmetricPersistent Circle Evacuation 
Nikos Leonardos, Aris Pagourtzis and Ioannis Papaioannou. 
We consider $(n,f)$evacuation on a circle, an evacuation problem of a hidden exit on the perimeter of a unit radius circle for $n>1$ robots, $f$ of which are faulty. All the robots start at the center of the circle and move with maximum speed~1. Robots must first find the exit and then move there to evacuate in minimum time. The problem is considered complete when all the honest robots know the correct position of the exit and the last honest robot has evacuated through the exit. During the search, robots can communicate wirelessly. We focus on symmetricpersistent algorithms, that is, algorithms in which all robots move directly to the circumference, start searching the circle moving in the same direction (cw or ccw), and do not stop moving around the circle before receiving information about the exit. We study the case of $(n,1)$ and $(n,2)$ evacuation. We first prove a lower bound of $1+\frac{4\pi}{n}+2\sin(\frac{\pi}{2}\frac{\pi}{n})$ for one faulty robot, even a crashfaulty one. We also observe an almost matching upper bound obtained by means of an earlier search algorithm. We finally study the case with two Byzantine robots and we provide an algorithm that achieves evacuation in time at most $3+\frac{6\pi}{n}$ , for $n\geq 9$, or at most $3+\frac{6\pi}{n}+\delta(n)$, for $n<9$, where $\delta(n) \leq 2\sin(\frac{3\pi}{2n})+ \sqrt{24\sin(\frac{3\pi}{2n})+4 \sin^{2}{(\frac{3\pi}{2n})}}2$. 
Thursday, September 9, 2021. Unsure about Portugal time zone? [Please check here]. 
THU. 9th  ROOM 1 

12:30  Welcoming ATMOS 
13:00  ALGOSENSORS Keynote : BERNHARD HAEUPLER (Auditorium): UniversallyOptimal Distributed Algorithms, (Congestion+Dilation)Competitive Oblivious Routing, and HopConstrained Network Design 
14:00  break 15 min and posters session 
14:15  ATMOS Session 1 
Niels Lindner, Christian Liebchen and Berenike Masing: Forward Cycle Bases and Periodic Timetabling 

Marc Goerigk, Anita Schöbel and Felix Spühler: A Phase I Simplex Method for Finding Feasible Periodic Timetables 

Vera Grafe and Anita Schöbel: Solving the periodic scheduling problem: An assignment approach in nonperiodic networks 

15:30  break 15 min and posters session 
15:45  ATMOS Session 2 
Matthias MüllerHannemann, Ralf Rückert, Alexander Schiewe and Anita Schöbel: Towards Improved Robustness of Public Transport by a MachineLearned Oracle 

SyuNing Johnn, Yiran Zhu, Andrés MiniguanoTrujillo and Akshay Gupte: Solving the Home Service Assignment, Routing, and Appointment scheduling (HSARA) problem with Uncertainties 

Daniela Gaul, Kathrin Klamroth and Michael Stiglmayr: Solving the Dynamic DialaRide Problem Using a RollingHorizon EventBased Graph 

17:00  break 15 min and posters session 
17:15  WAOA keynote : DANIEL LOKSHTANOV (Auditorium) 
18:15  break 15 min and posters session 
18:30  ATMOS Session 3: chairs: Matthias MüllerHannemann and Federico Perea 
Robert Benkoczi, Binay Bhattacharya, Yuya Higashikawa, Tsunehiko Kameda, Naoki Katoh and Junichi Teruyama: Locating Evacuation Centers Optimally in Path and Cycle Networks 

Diptendu Chatterjee and Bimal K. Roy: An Improved Scheduling Algorithm for Traveling Tournament Problem with Maximum Trip Length Two 

19:20  break 10 min 
19:30  ATMOS Business meeting and BestPaper Award 
20:00  end of the day 
Friday, September 10, 2021. Unsure about Portugal time zone? [Please check here]. 
FRI. 10th  ROOM 1  

13:00  ATMOS Session 4  
Peter Damaschke: Distancebased Solution of Patrolling Problems with Individual Waiting Times 

Marco Silva, Joao Pedro Pedroso, Ana Viana and Xenia Klimentova: A branchpriceandcut algorithm for stochastic crowd shipping lastmile delivery with correlated marginals 

Elia Costa and Francesco Silvestri: On the Bike Spreading Problem 

14:15  break 15 min and posters session  
14:30  ATMOS Session 5  
Guvenc Sahin, Amin Ahmadi Digehsara and Ralf Borndörfer: Efficient Algorithms for the MultiPeriod Line Planning Problem in Public Transportation (short paper) 

Hector Gatt, JeanMarie Freche, Fabien Lehuede and Thomas Yeung: A column generationbased heuristic for the Line Planning Problem with Service Levels (short paper) 

Natividad GonzálezBlanco, Antonio J. Lozano, Juan A. Mesa and Vladimir Marianov: An integrated model for rapid and slow transit network design (short paper) 

15:45  break 15 min and posters session  
16:00  ATMOS keynote : ANITA SCHÖBEL (Auditorium): Approaches for integrated planning: The case of public transport optimization 

17:00  break 15 min and posters session  
17:15  ATMOS Session 6  
Daniel Chen, Christian Sommer and Daniel Wolleb: Fast Map Matching with VertexMonotone Fréchet Distance 

Payas Rajan, Moritz Baum, Michael Wegner, Tobias Zündorf, Christian West, Dennis Schieferdecker and Daniel Delling: Robustness Generalizations of the Shortest Feasible Path Problem for Electric Vehicles 

Vassilissa LehouxLebacque and Christelle Loiodice: Transfer customization with the TripBased Public Transit Routing Algorithm 

18:30  break 15 min and posters session  
18:45  ATMOS Session 7 chair: Matthias MüllerHannemann 

Niels Lindner, Pedro Maristany de Las Casas and Philine Schiewe: Optimal Forks: Preprocessing SingleSource Shortest Path Instances with Interval Data 

Carlo S. Sartori, Pieter Smet and Greet Vanden Berghe: Efficient durationbased workload balancing for interdependent vehicle routes 

19:35  end of the day 
ATMOS Keynote (Friday, Sept. 10, 16:0017:00) 
Approaches for integrated planning: The case of public transport optimization 
ANITA SCHÖBEL, University of Kaiserslautern and ITWN 
Approaches for integrated planning: The case of public transport optimization Many realworld problems are treated sequentially. One prominent example for such a sequential process is public transport optimization: One starts with network design, then plans lines and their frequencies. Based on these, the timetable is determined, and later on the vehicles’ and drivers’ schedules. The sequential procedure sketched above can be regarded as a Greedy approach: in each planning stage one aims at the best one can do. This usually leads to suboptimal solutions. On the other hand, in public transport optimization many of the mentioned single steps are already NP hard such that solving the integrated problem to optimality seems to be out of scope. We introduce the price of sequentiality to measure how much can be gained by integrated approaches. We then present different approaches for integrated optimization and illustrate them for the case of public transport optimization. Among them is the Eigenmodel as a framework for (heuristic) integrated approaches. 
Monday, September 6, 2021. Unsure about Portugal time zone? [Please check here]. 
MON. 6th  ROOM 1  ROOM 2  ROOM 3  

12:30  Welcoming ESA  
13:00  ESA Track A: Graph algorithms chair: Ran Duan 
ESA Track A: Scalable algorithms chair: Benjamin Doerr 
ESA Track A: Computationally hard problems chair: Holger Dell 

Michał Dębski, Marta Piecyk and Paweł Rzążewski: Faster 3coloring of smalldiameter graphs 
Claire Mathieu and Hang Zhou: A Simple Algorithm for Graph Reconstruction 
Jana Cslovjecsek, Friedrich Eisenbrand, Michał Pilipczuk, Moritz Venzin and Robert Weismantel: Efficient sequential and parallel algorithms for multistage stochastic integer programming using proximity 

Katarzyna Paluch and Mateusz Wasylkiewicz: Restricted tmatchings via halfedges 
Panagiotis Charalampopoulos, Tomasz Kociumaka, Solon Pissis and Jakub Radoszewski: Faster Algorithms for Longest Common Substring 
Leon Kellerhals, Malte Renken and Philipp Zschoche: Parameterized Algorithms for Diverse Multistage Problems 

Éric Colin de Verdière and Thomas Magnard: An FPT algorithm for the embeddability of graphs into twodimensional simplicial complexes 
Krzysztof Potępa: Faster Deterministic Modular Subset Sum 
Marek Cygan, Alexander Kulikov, Ivan Mihajlin, Maksim Nikolaev and Grigory Reznikov: Minimum Common String Partition: Exact Algorithms 

14:15  break 15 min and posters session  
14:30  ESA Track A: Graph algorithms chair: Édouard Bonnet 
ESA Track A: Optimization chair: Ilan Cohen 
ESA Track A: Orientations and representatives chair: Jakub Łącki 

Thomas Bläsius, Tobias Friedrich and Maximilian Katzmann: Efficiently Approximating Vertex Cover on ScaleFree Networks with Underlying Hyperbolic Geometry 
Lin Chen, Hossein Esfandiari, Thomas Fu, Vahab Mirrokni and Qian Yu: Feature Cross Search via Submodular Optimization 
Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul, Ely Porat and Clifford Stein: Incremental Edge Orientation in Forests 

Eden Pelleg and Stanislav Živný: Additive Sparsification of CSPs 
Yaron Fairstein, Ariel Kulik and Hadas Shachnai: Modular and Submodular Optimization with Multiple Knapsack Constraints via Fractional Grouping 
Therese Biedl, Anna Lubiw, Anurag Murty Naredla, Peter Dominik Ralbovsky and Graeme Stroud: Distant Representatives for Rectangles in the Plane 

Benoit Larose, Petar Marković, Barnaby Martin, Daniel Paulusma, Siani Smith and Stanislav Živný: QCSP on Reflexive Tournaments 
Marilena Leichter, Benjamin Moseley and Kirk Pruhs: An Efficient Reduction of a Gammoid to a Partition Matroid 
Evripidis Bampis, Christoph Dürr, Thomas Erlebach, Murilo S. de Lima, Nicole Megow and Jens Schlöter: Orienting (hyper)graphs under explorable stochastic uncertainty 

15:45  break 15 min and posters session  
16:00  Keynote ESA : AARON ROTH (Auditorium): User Friendly Power Tool for Deriving Online Learning Algorithms 

17:00  break 15 min and posters session  
17:15  ESA Best Papers Session chairs: Petra Mutzel and Rasmus Pagh 

Track A best student paper: Wojciech Nadara, Mateusz Radecki, Marcin Smulewicz and Marek Sokołowski: Determining 4edgeconnected components in linear time 
Track B best student paper: Florian Wörz and JanHendrik Lorenz: Evidence for LongTails in SLS Algorithms 

Track A best paper: Zhiyang He, Jason Li and Magnus Wahlström: Nearlineartime, Optimal Vertex Cut Sparsifiers in Directed Acyclic Graphs 

Track B best paper: Simon D. Fink, Matthias Pfretzschner and Ignaz Rutter: Experimental Comparison of PCTrees and PQTrees 

18:30  ESA TestofTime Award: Rasmus Pagh, Flemming Friche Rodler Cuckoo Hashing 

18:55  end of the day 
Tuesday, September 7, 2021.Unsure about Portugal time zone? [Please check here]. 
TUE. 7th>  ROOM 1  ROOM 2  ROOM 3  

13:00  ESA Track B: Graphs chair: Andrea Marino 
ESA Track A: Spaceefficient data structures chair: Rasmus Pagh 
ESA Track A: Parameterized algorithms chair: Akanksha Agrawal 

Saman Ahmadi, Guido Tack, Daniel Harabor and Philip Kilby: Biobjective Search with Bidirectional A* 
Moses Ganardi: Compression by Contracting StraightLine Programs 
Katrin Casel, Tobias Friedrich, Davis Issac, Aikaterini Niklanovits and Ziena Zeif: Balanced Crown Decomposition for Connectivity Constraints 

Thomas Bläsius, Tobias Friedrich and Christopher Weyand: Efficiently Computing Maximum Flows in ScaleFree Networks 
Ian Munro, Patrick K. Nicholson, Louisa Seelbach Benkner and Sebastian Wild: Hypersuccinct Trees – New universal tree source codes for optimal compressed tree data structures and range minima 
Daniel Neuen: Isomorphism Testing Parameterized by Genus and Beyond 

Lars Gottesbüren, Tobias Heuer, Peter Sanders, Christian Schulz and Daniel Seemaier: Deep Multilevel Graph Partitioning 
Davide Bilò, Sarel Cohen, Tobias Friedrich and Martin Schirneck: NearOptimal Deterministic SingleSource Distance Sensitivity Oracles 
Radu Curticapean, Holger Dell and Thore Husfeldt: Modular counting of subgraphs: Matchings, matchingsplittable graphs, and paths 

14:15  break 15 min and posters session  
14:30  ESA Track B: Optimization chair: Petra Berenbrink 
ESA Track A: Dynamic data structures chair: Gramoz Goranci 
ESA Track A: Online algorithms chair: Pierre Fraigniaud 

Markus Anders and Pascal Schweitzer: Parallel Computation of Combinatorial Symmetries 
Sepehr Assadi and Shay Solomon: Fully Dynamic Set Cover via Hypergraph Maximal Matching: An Optimal Approximation Through a Local Approach 
Sujoy Bhore and Csaba Toth: Online Euclidean Spanners 

Kolja Junginger, Ioannis Mantas, Evanthia Papadopoulou, Martin Suderland and Chee Yap: Certified Approximation Algorithms for the Fermat Point and nEllipses 
Hendrik Fichtenberger, Monika Henzinger and Wolfgang Ost: Differentially Private Algorithms for Graphs Under Continual Observation 
Nikhil Ayyadevara and Ashish Chiplunkar: The Randomized Competitive Ratio of Weighted $k$Server is at Least Exponential 

Aaron Bernstein, Aditi Dudeja and Seth Pettie: Incremental SCC Maintenance in Sparse Graphs 
Thomas Lavastida, Benjamin Moseley, R. Ravi and Chenyang Xu: Learnable and InstanceRobust Predictions for Online Matching, Flows and Load Balancing 

15:45  break 15 min and posters session  
16:00  Keynote ESA : FRAUKE LIERS (Auditorium): Network Planning and Routing Problems Over Time: Models, Complexity and Algorithms 

17:00  break 15 min and posters session  
17:15  ESA Track B: Data structures chair: Gerth Brodal 
ESA Track A: Quantum algorithms chair: Simon Apers 
ESA Track A: Game theory chair: Chaitanya Swamy 

Peter Sanders, Marvin Williams and Roman Dementiev: Engineering MultiQueues: Fast Relaxed Concurrent Priority Queues 
Yassine Hamoudi: Quantum SubGaussian Mean Estimator 
Ryoga Mahara: Extension of Additive Valuations to General Valuations on the Existence of EFX 

David Lee, Samuel McCauley, Shikha Singh and Max Stein. Telescoping Filter: A Practical Adaptive Filter 
Ojas Parekh and Kevin Thompson: Beating Random Assignment for Approximating Quantum 2Local Hamiltonian Problems 
Alexander Braun, Matthias Buttkus and Thomas Kesselheim: Asymptotically Optimal Welfare of Posted Pricing for Multiple Items with MHR Distributions 

18:05  break 15 min and posters session  
18:20  ESA Track B: Strings chair: Henning Meyerhenke 
ESA Track A: Geometric data structures chair: Laxman Dhulipala 
ESA Track A: Optimization chair: Omri Weinstein 

Nico Bertram, Jonas Ellert and Johannes Fischer: Lyndon Words Accelerate Suffix Sorting 
Jean Cardinal, John Iacono and Grigorios Koumoutsos: WorstCase Efficient Dynamic Geometric Independent Set 
Daniel Lokshtanov, Subhash Suri and Jie Xue: Efficient Algorithms for Least Square Piecewise Polynomial Regression 

Dominik Kempa and Ben Langmead: Fast and SpaceEfficient Construction of AVL Grammars from the LZ77 Parsing 
Timothy M. Chan and Zhengcheng Huang: Dynamic Colored Orthogonal Range Searching 
Daniel Dadush, Zhuan Khye Koh, Bento Natura and László A. Végh: An Accelerated NewtonDinkelbach Method and its Application to Two Variables Per Inequality Systems 

Grigorios Loukides and Solon Pissis: Bidirectional String Anchors: a New String Sampling Mechanism 
Younan Gao and Meng He: Space Efficient TwoDimensional Orthogonal Colored Range Counting 
Yishu Wang, Arnaud Mary, MarieFrance Sagot and Blerina Sinaimeri: A general framework for enumerating equivalence classes of solutions 

19:35  end of the day 
Wednesday, September 8, 2021. Unsure about Portugal time zone? [Please check here]. 
WED. 8th  ROOM 1  ROOM 2  ROOM 3 

13:00  Keynote IPEC : FRANK STEPHAN & BAKHADYR KHOUSSAINOV (Auditorium): Parity Games  Background and Algorithms 

14:00  break 15 min and posters session  
14:15  ESA Track A: Graph algorithms chair: Christos Zaroliagis 
ESA Track A: Computational geometry chair: Jeff Phillips 
ESA Track A: Sublinear algorithms chair: Clément Canonne 
Zdenek Dvorak and Abhiruk Lahiri: Approximation schemes for bounded distance problems on fractionally treewidthfragile graphs 
Jean Cardinal, Justin Dallant and John Iacono: An Instanceoptimal Algorithm for Bichromatic Rectangular Visibility 
Hu Ding: Stability Yields Sublinear Time Algorithms for Geometric Optimization in Machine Learning 

Maor Akav and Liam Roditty: A unified approach for all pairs approximate shortest paths in weighted undirected graphs 
Carlos Alegría, Ioannis Mantas, Evanthia Papadopoulou, Marko Savić, Hendrik Schrezenmaier, Carlos Seara and Martin Suderland: The Voronoi Diagram of Rotating Rays with applications to Floodlight Illumination 
Mark de Berg, Morteza Monemizadeh and Yu Zhong: kCenter Clustering with Outliers in the SlidingWindow Model 

Timothy M. Chan: AllPairs Shortest Paths for RealWeighted Undirected Graphs with Small Additive Error 
Anna Lubiw and Anurag Murty Naredla: The Visibility Center of a Simple Polygon 
Sepehr Assadi, Deeparnab Chakrabarty and Sanjeev Khanna: Graph Connectivity and Single Element Recovery via Linear and OR Queries 

15:30  break 15 min and posters session  
15:45  ESA Track A: Flows and cuts chair: Jason Li 
ESA Track A: Computational geometry chair: Zac Friggstad 
ESA Track A: Hardness results chair: Marvin Künnemann 
William Maxwell and Amir Nayyeri: Generalized maxflows and mincuts in simplicial complexes 
Sariel HarPeled and Timothy Zhou: Improved Approximation Algorithms for Tverberg Partitions 
Pavel Dvořák, Michal Koucký, Karel Král and Veronika Slívová: Data Structures Lower Bounds and Popular Conjectures 

Evangelos Kosinas, Loukas Georgiadis and Giuseppe F. Italiano: Computing the 4EdgeConnected Components of a Graph in Linear Time 
Alejandro FloresVelazco and David Mount: BoundarySensitive Approach for Approximate NearestNeighbor Classification 
David Caballero, Timothy Gomez, Robert Schweller and Tim Wylie: Covert Computation in Staged SelfAssembly: Verification is PSPACEcomplete 

Karthekeyan Chandrasekaran and Weihang Wang: ℓpnorm Multiway Cut 
Jasper C.H. Lee, Jerry Li, Christopher Musco, Jeff Phillips and Wai Ming Tai: Finding an Approximate Mode of a Kernel Density Estimate 
Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń and Wiktor Zuba: Hardness of Detecting Abelian and Additive Square Factors in Strings 

17:00  break 15 min and posters session  
17:15  ESA Track A: Graph algorithms chair: Zac Friggstad 
ESA Track A: Optimization and scheduling chair: Frances Rosamond 

Thomas Bläsius, Simon D. Fink and Ignaz Rutter: Synchronized Planarity with Applications to Constrained Planarity Problems 
Tomas MartinezMunoz and Andreas Wiese: FPT and FPTapproximation algorithms for Unsplittable Flow on Trees 

Boris Klemz: Convex drawings of hierarchical graphs in linear time, with applications to planar graph morphing 
Fabrizio Grandoni, Tobias Mömke and Andreas Wiese: Faster (1+epsilon)approximation for Unsplittable Flow on a Path via resource augmentation and back 

Ramanujan M. Sridharan: On Approximate Compressions for Connected Minorhitting Sets 
Klaus Jansen and Malin Rau: Closing the gap for single resource constraint scheduling 

Joergen BangJensen, Kristine Vitting Klinkby and Saket Saurabh: kDistinct Branchings Admits a Polynomial Kernel 
Guillaume Sagnol and Daniel Schmidt Genannt Waldschmidt: Restricted Adaptivity in Stochastic Scheduling 

18:55  break 15 min and posters session  
19:10  ESA Business meeting  
20:10  end of the day 
Thursday, September 9, 2021. Unsure about Portugal time zone? [Please check here]. 
THU. 9th  ROOM 2  

12:30  Welcoming WAOA  
13:00  ALGOSENSORS Keynote : BERNHARD HAEUPLER (Auditorium): UniversallyOptimal Distributed Algorithms, (Congestion+Dilation)Competitive Oblivious Routing, and HopConstrained Network Design 

14:00  break 15 min and posters session  
14:15  WAOA Session 1  
Waldo Gálvez, Francisco SanhuezaMatamala and José A. Soto: Approximation Algorithms for VertexConnectivity Augmentation on the Cycle 

Václav Blažej, Pratibha Choudhary, Dušan Knop, Jan Matyáš Křišťan, Ondrej Suchy and Tomáš Valla: Constant Factor Approximation for Tracking Paths and Fault Tolerant Feedback Vertex Set 

Hao Sun: An Improved Approximation Bound for Minimum Weight Dominating Set on Graphs of Bounded Arboricity 

15:30  break 15 min and posters session  
15:45  WAOA Session 2  
Szymon Dudycz, Pasin Manurangsi and Jan Marcinkowski: Tight Inapproximability of Minimum Maximal Matching on Bipartite Graphs and Related Problems 

Toshihiro Fujito and Takumi Tatematsu: On bMatchings and bEdge Dominating Sets: A 2Approximation Algorithm for the 4Edge Dominating Set Problem 

Dylan Huizing and Guido Schäfer: The Traveling kMedian Problem: Approximating Optimal Network Coverage 

17:00  break 15 min and posters session  
17:15  WAOA keynote : DANIEL LOKSHTANOV (Auditorium)  
18:15  break 15 min and posters session  
18:30  WAOA Session 3  
G. Jaykrishnan and Asaf Levin: EPTAS for Load Balancing Problem on Parallel Machines with a Nonrenewable Resource 

Leah Epstein: Several methods of analysis for cardinality constrained bin packing 

19:20  end of the day 
Friday, September 10, 2021. Unsure about Portugal time zone? [Please check here]. 
FRI. 10th  ROOM 2 

13:00  WAOA Session 4 
Ilan Cohen, Izack Cohen and Iyar Zaks: Weighted completion time minimization for capacitated parallel machines 

Marten Maack, Friedhelm Meyer Auf der Heide and Simon Pukrop: Server Cloud Scheduling 

B.Tauer, and L. Vargas Koch: FIFO and Randomized Competitive Packet Routing Games 

14:15  break 15 min and posters session 
14:30  WAOA Session 5 
Jeff Giliberti and Andreas Karrenbauer: Improved Online Algorithm for Fractional Knapsack in the Random Order Model 

Yann Disser, Max Klimm and David Weckbecker: Fractionally Subadditive Maximization under an Incremental Knapsack Constraint 

Marcin Bienkowski, Martin Böhm, Martin Koutecký, Thomas Rothvoß, Jiří Sgall and Pavel Veselý: Improved Analysis of Online Balanced Clustering 

15:45  break 15 min and posters session 
16:00  ATMOS keynote : ANITA SCHÖBEL (Auditorium): Approaches for integrated planning: The case of public transport optimization 
17:00  break 15 min and posters session 
17:15  WAOA Session 6 
Stavros Kolliopoulos and Antonis Skarlatos: PrecedenceConstrained Covering Problems with Multiplicity Constraints 

Nikhil Bansal and Ilan Cohen: Contention Resolution, Matrix Scaling and Fair Allocation 

18:05  end of the day 
WAOA Keynote (Friday, Sept. 10, 17:1518:15) 
How to Navigate Through Obstacles (and How to Place Them) 
Daniel Lokshtanov, University of California, Santa Barbara 
Consider an agent that has to move from a source point s to a destination point t through an environment. The environment can be the plane, multidimensional space, or a graph. Suppose now that the environment is littered with (possibly overlapping) obstacles that obstruct the path from s to t. What is the minimum number of obstacles that has to be removed so that the agent can move unobstructed from the source to the destination? This is a fundamental problem with applications ranging from sensor networks to robotics, and it has been intensively studied under different names. In this talk we will survey the state of the art for the problem, from the perspective of approximation algorithms, hardness of approximation, and parameterized algorithms. We will also consider the dual problem of placing the minimum number of obstacles between the source and the destination so that there is no unobstructed path from the source to the destination. 
Wednesday, September 8, 2021. Unsure about Portugal time zone? [Please check here]. 
WED. 8th  ROOM 4  

12:30  Welcoming IPEC  
13:00  Keynote IPEC : FRANK STEPHAN & BAKHADYR KHOUSSAINOV (Auditorium): Parity Games  Background and Algorithms 

14:00  break 15 min and posters session  
14:15  IPEC Session 1  
Huib Donkers, Bart M. P. Jansen and Michal Wlodarczyk. Preprocessing for Outerplanar Vertex Deletion: An Elementary Kernel of Quartic Size 

Akanksha Agrawal, Aditya Anand and Saket Saurabh. A Polynomial Kernel for deletion to Ptolemaic Graphs 

Lawqueen Kanesh, Jayakrishnan Madathil, Abhishek Sahu, Saket Saurabh and Shaily Verma. A Polynomial Kernel for Bipartite Permutation Vertex Deletion 

15:30  break 15 min and posters session  
15:45  IPEC Session 2  
Maël Dumas, Anthony Perez and Ioan Todinca. Polynomial kernels for strictly chordal edge modification problems 

Gabriel Bathie, Nicolas Bousquet and Théo Pierron. (Sub)linear kernels for edge modification problems towards structured graph classes 

Yixin Cao and Yuping Ke. Improved Kernels for Edge Modification Problems 

17:00  break 15 min and posters session  
17:15  IPEC Session 3  
Alejandro Grez, Filip Mazowiecki, Michał Pilipczuk, Gabriele Puppis and Cristian Riveros. Dynamic data structures for timed automata acceptance 

Max Bannach, Zacharias Heinrich, Ruediger Reischuk and Till Tantau. Dynamic Kernels for Hitting Sets and Set Packing 

Vít Jelínek, Michal Opler and Jakub Pekárek. Long paths make patterncounting hard, and deep trees make it harder 

Julio Araujo, Marin Bougeret, Victor A. Campos and Ignasi Sau. Kernelization of Maximum Minimal Vertex Cover 

18:55  break 15 min and posters session  
19:10  IPEC Award session  
20:10  end of the day 
Thursday, September 9, 2021. Unsure about Portugal time zone? [Please check here]. 
THU. 9th  ROOM 4 

13:00  ALGOSENSORS Keynote : BERNHARD HAEUPLER (Auditorium): UniversallyOptimal Distributed Algorithms, (Congestion+Dilation)Competitive Oblivious Routing, and HopConstrained Network Design 
14:00  break 15 min and posters session 
14:15  IPEC Session 4 
Laurent Bulteau, Bertrand Marchand and Yann Ponty. A new parametrization for independent set reconfiguration and applications to RNA kinetics 

Hans L. Bodlaender, Carla Groenland and Céline M. F. Swennenhuis. Parameterized Complexities of Dominating and Independent Set Reconfiguration 

Andreas Emil Feldmann and Ashutosh Rai. On Extended Formulations for Parameterized Steiner Trees 

15:30  break 15 min and posters session 
15:45  IPEC Session 5 
Shaohua Li and Marcin Pilipczuk. Hardness of Metric Dimension in Graphs of Constant Treewidth 

Guillaume Ducoffe. Maximum Matching in almost linear time on the graphs of bounded cliquewidth 

Guillaume Ducoffe. Optimal centrality computations within bounded cliquewidth graphs 

17:00  break 15 min and posters session 
17:15  WAOA keynote : DANIEL LOKSHTANOV (Auditorium) 
18:15  break 15 min and posters session 
18:30  IPEC business meeting 
19:20  end of the day 
Friday, September 10, 2021. Unsure about Portugal time zone? [Please check here]. 
FRI. 10th  ROOM 4 

13:00  IPEC Tutorial Session 6 
Tutorial with Édouard Bonnet Twinwidth 

14:15  break 15 min and posters session 
14:30  IPEC Session 7 
Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé and Rémi Watrigant. Twinwidth and polynomial kernels 

Jakub Balabán and Petr Hlineny. TwinWidth is Linear in the Poset Width 

Dennis Fischer, Tim A. Hartmann, Stefan Lendl and Gerhard J. Woeginger. An Investigation of the Recoverable Robust Assignment Problem 

15:45  break 15 min and posters session 
16:00  ATMOS keynote : ANITA SCHÖBEL (Auditorium): Approaches for integrated planning: The case of public transport optimization 
17:00  break 15 min and posters session 
17:15  IPEC Session 8 
Haozhe An, Mohit Jayanti Gurumukhani, Russell Impagliazzo, Michael Jaber, Marvin Künnemann and Maria Paula Parga Nina. The finegrained complexity of multidimensional ordering properties 

Akanksha Agrawal, Ravi Kiran Allumalla and Varun Teja Dhanekula. FPT Algorithms for Some Parameterized Problems Under GapETH/td>  
Hugo Jacob, Thomas Bellitto, Oscar Defrain and Marcin Pilipczuk. Close relatives (of Feedback Vertex Set), revisited/td>  
18:30  break 15 min and posters session 
18:45  IPEC Session 9 
Igor Razgon. Classification of OBDD size for monotone 2CNFs 

Vikraman Arvind and Venkatesan Guruswami. CNF Satisfiability in a Subspace and Related Problems 

Elisabet Burjons and Peter Rossmanith. Lower Bounds for Conjunctive and Disjunctive Turing Kernels 

20:25  end of the day (and posters session) 
Monday, September 6, 2021. Unsure about Portugal time zone? [Please check here]. 
MON. 6th  ROOM 4 

12:30  Welcoming ALGOCLOUD 
13:00  ALGOCLOUD Session 1 
Shahin Kamali and Pooya Nikbakht: On the FaultTolerant Online Bin Packing Problem 

Léonard Lys, Arthur Micoulet and Maria PotopButucaru. RSWAP: Relay based atomic crosschain swap protocol 

Matthew Connor. Brief Announcement: On the Distributed Construction of Stable Networks in Polylogarithmic Parallel Time 

14:15  break 15 min and posters session 
14:30  Tutorial with Stefan Schmid: SelfAdjusting Networks: Enablers, Algorithms, Complexity 
15:45  break 15 min and posters session 
16:00  Keynote ESA : AARON ROTH (Auditorium): User Friendly Power Tool for Deriving Online Learning Algorithms 
17:00  break 15 min and posters session 
17:15  Tutorial with Amitabh Trehan: Selfhealing Distributed Algorithms 
18:30  end of the day 
Tuesday, September 7, 2021.Unsure about Portugal time zone? [Please check here]. 
TUE. 7  ROOM 4 

13:00  Keynote ALGOCLOUD: CHRISTIAN SCHEIDELER CloudAssisted PeertoPeer Systems 
14:15  break 15 min and posters session 
14:30  Tutorial with Maria PotopButucaru: Gaming the Decentralized Finance 
15:45  break 15 min and posters session 
16:00  Keynote ESA : FRAUKE LIERS (Auditorium): Network Planning and Routing Problems Over Time: Models, Complexity and Algorithms 
17:00  break 15 min and posters session 
17:15  ALGOCLOUD Session 2 
Bugra Caskurlu, Utku Acikalin, Piotr Wojciechowski and K. Subramani. New Results on TestCost Minimization in Database Migration 

Anna Katharina Hildebrandt, Ernst Althaus and Andreas Hildebrandt. Privately querying Privacy: privacy estimation with guaranteed privacy of user and database party 

18:05  break 15 min and posters session 
18:20  ALGOCLOUD Business meeting 
19:35  end of the day 
Tutorial 1 (Monday, Sept. 6, 14:3015:45) 
SelfAdjusting Networks: Enablers, Algorithms, Complexity 
Stefan Schmid, University of Vienna 
Network traffic is growing explosively, and nextgeneration workloads, e.g., related to (distributed) machine learning and artificial intelligence, will further increase the amount of traffic headed for and between the world’s data centers. This quickly growing demand pushes today’s widearea and datacenter networks towards their capacity limits. While over the years, several interesting new network architectures have been proposed to improve the efficiency and performance of such networks, especially in the context of data centers, these networks often have in common that their topology is fixed and cannot be reconfigured to the traffic demand they serve. This tutorial discusses a different approach to operate networks: reconfigurable "selfadjusting" networks whose topology adjusts to the workload in an online manner. Reconfigurable networks are enabled by emerging optical technologies, allowing to quickly change the physical topology at runtime. This technology also introduces a vision of demandaware networks which tap a new optimization opportunity: empirical and measurement studies show that traffic workloads feature spatial and temporal structure, which in principle could be exploited by reconfigurable networks. However, while the technology of such reconfigurable networks is evolving at a fast pace, these networks lack theoretical foundations: models, metrics, and algorithms  we have fallen behind the curve. The objective of this tutorial is to help bridge this gap, and introduce to the ALGO community a rich and potentially impactful research area, which touches many core topics of the conference. We first discuss technological enablers and report on motivating empirical studies. Our main focus in this tutorial then is on the new models and algorithmic challenges introduced by this field. In particular, we will review existing algorithms and complexity results, and highlight future research directions. 
Tutorial 2 (Monday, Sept. 6, 17:1518:30) 
Selfhealing Distributed Algorithms 
Amitabh Trehan, Durham University 
Resilience and faulttolerance are highly desirable properties for networks and often distributed algorithms are designed with this purpose in mind. Selfhealing is one such faulttolerance paradigm which seeks to maintain a desirable state of the system despite attack accepting only a short disruption. The concept of selfhealing appears in various forms ranging from autonomic networks to practical networks to distributed algorithms. We look at the later setting formalising selfhealing as a game on graphs where a powerful adversary deletes/inserts nodes and the network responds by adding/dropping edges locally in a distributed manner while seeking to maintain global invariants. This requires the network to be reconfigurable e.g. in the P2PCONGEST model (with limited message sizes). We look at various results in this setting building up selfhealing resilience by adding topological properties such as connectivity, diameter, stretch, expansion, and routing in a simultaneous manner. 
Tutorial 3 (Monday, Sept. 7, 14:3015:45) 
Gaming the Decentralized Finance 
Maria PotopButucaru, , Sorbonne Université  LIP6 
Decentralized finance opens a new research field: reliable distributed economical systems that is a cross research between classical distributed systems and mathematical models for economical systems. Blockchain technology is today at the core of decentralized finance. Differently from the classical distributed systems, blockchain technology faces complex faults and behaviors including rational. Interestingly, when rational behaviors are combined with classical faults (e.g. Byzantine behaviors) established results in distributed computing need to be revisited. This talk reports several results related to robustness of distributed abstractions used in blockchain technologies to Byzantine and rational behaviors analyzed through the lens of game theory. 