Joining the meeting

Please click on the image to access the meeting platform. Access will be free until Saturday, September 4th. After that, access will be restricted to users registered in ALGO 2021.

Programme

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

DOWNLOAD THE PROGRAMME IN PDF

Daily Schedule (UTC+1, Lisbon, Portugal)

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 3-coloring of small-diameter 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 Fault-Tolerant Online Bin Packing Problem
Katarzyna Paluch and Mateusz Wasylkiewicz:
Restricted t-matchings via half-edges		 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 Potop-Butucaru.
R-SWAP: Relay based atomic cross-chain swap protocol
Éric Colin de Verdière and Thomas Magnard:
An FPT algorithm for the embeddability of graphs into two-dimensional 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 Scale-Free 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:
Self-Adjusting 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 4-edge-connected components in linear time 		Track B best student paper:
Florian Wörz and Jan-Hendrik Lorenz:
Evidence for Long-Tails in SLS Algorithms 		Tutorial with Amitabh Trehan:
Self-healing Distributed Algorithms
Track A best paper:
Zhiyang He, Jason Li and Magnus Wahlström:
Near-linear-time, Optimal Vertex Cut Sparsifiers in Directed Acyclic Graphs
Track B best paper:
Simon D. Fink, Matthias Pfretzschner and Ignaz Rutter:
Experimental Comparison of PC-Trees and PQ-Trees
18:30 ESA Test-of-Time 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:
Space-efficient data structures
chair: Rasmus Pagh		 ESA Track A:
Parameterized algorithms
chair: Akanksha Agrawal		 ALGOCLOUD Keynote
Saman Ahmadi, Guido Tack, Daniel Harabor and Philip Kilby:
Bi-objective Search with Bi-directional A*		 Moses Ganardi:
Compression by Contracting Straight-Line Programs		 Katrin Casel, Tobias Friedrich, Davis Issac, Aikaterini Niklanovits and Ziena Zeif:
Balanced Crown Decomposition for Connectivity Constraints		 CHRISTIAN SCHEIDELER :
Cloud-Assisted Peer-to-Peer Systems
Thomas Bläsius, Tobias Friedrich and Christopher Weyand:
Efficiently Computing Maximum Flows in Scale-Free 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:
Near-Optimal Deterministic Single-Source Distance Sensitivity Oracles		 Radu Curticapean, Holger Dell and Thore Husfeldt:
Modular counting of subgraphs: Matchings, matching-splittable 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:
On-line 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 Potop-Butucaru:
Gaming the Decentralized Finance
Kolja Junginger, Ioannis Mantas, Evanthia Papadopoulou, Martin Suderland and Chee Yap:
Certified Approximation Algorithms for the Fermat Point and n-Ellipses		 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 Instance-Robust 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 Sub-Gaussian 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 Test-Cost 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 2-Local 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:
Worst-Case 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 Space-Efficient 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 Newton-Dinkelbach 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 Two-Dimensional Orthogonal Colored Range Counting		 Yishu Wang, Arnaud Mary, Marie-France 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 treewidth-fragile graphs		 Jean Cardinal, Justin Dallant and John Iacono:
An Instance-optimal 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:
k-Center Clustering with Outliers in the Sliding-Window Model		 Akanksha Agrawal, Aditya Anand and Saket Saurabh.
A Polynomial Kernel for deletion to Ptolemaic Graphs
Timothy M. Chan:
All-Pairs Shortest Paths for Real-Weighted 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 max-flows and min-cuts in simplicial complexes		 Sariel Har-Peled 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 4-Edge-Connected Components of a Graph in Linear Time		 Alejandro Flores-Velazco and David Mount:
Boundary-Sensitive Approach for Approximate Nearest-Neighbor Classification		 David Caballero, Timothy Gomez, Robert Schweller and Tim Wylie:
Covert Computation in Staged Self-Assembly: Verification is PSPACE-complete		 Gabriel Bathie, Nicolas Bousquet and Théo Pierron.
(Sub)linear kernels for edge modification problems towards structured graph classes
Karthekeyan Chandrasekaran and Weihang Wang:
ℓp-norm 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 Martinez-Munoz and Andreas Wiese:
FPT and FPT-approximation 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 Minor-hitting 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 pattern-counting hard, and deep trees make it harder
Joergen Bang-Jensen, Kristine Vitting Klinkby and Saket Saurabh:
k-Distinct 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):
Universally-Optimal Distributed Algorithms, (Congestion+Dilation)-Competitive Oblivious Routing, and Hop-Constrained 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 Sanhueza-Matamala and José A. Soto:
Approximation Algorithms for Vertex-Connectivity Augmentation on the Cycle		 Louis Esperet, Sébastien Julliot
and Arnaud de Mesmay:
Distributed coloring and the local structure of unit-disk 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 non-periodic 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üller-Hannemann, Ralf Rückert, Alexander Schiewe and Anita Schöbel:
Towards Improved Robustness of Public Transport by a Machine-Learned 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
Syu-Ning Johnn, Yiran Zhu, Andrés Miniguano-Trujillo and Akshay Gupte:
Solving the Home Service Assignment, Routing, and Appointment scheduling (H-SARA) problem with Uncertainties		 Toshihiro Fujito and Takumi Tatematsu:
On b-Matchings and b-Edge Dominating Sets: A 2-Approximation Algorithm for the 4-Edge 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 clique-width
Daniela Gaul, Kathrin Klamroth and Michael Stiglmayr:
Solving the Dynamic Dial-a-Ride Problem Using a Rolling-Horizon Event-Based Graph		 Dylan Huizing and Guido Schäfer:
The Traveling k-Median Problem: Approximating Optimal Network Coverage		 Guillaume Ducoffe.
Optimal centrality computations within bounded clique-width 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üller-Hannemann
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 Non-renewable 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:
Distance-based 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 Self-Eliminations		 Tutorial with Édouard Bonnet
Twin-width
Marco Silva, Joao Pedro Pedroso, Ana Viana and Xenia Klimentova:
A branch-price-and-cut algorithm for stochastic crowd shipping last-mile 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 Connectivity-Preserving 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 Multi-Period 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 ell-p Unit Disks
in the Wireless Model		 Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé and Rémi Watrigant.
Twin-width and polynomial kernels
Hector Gatt, Jean-Marie Freche, Fabien Lehuede and Thomas Yeung:
A column generation-based 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 Symmetric-Persistent Circle Evacuation		 Jakub Balabán and Petr Hlineny.
Twin-Width is Linear in the Poset Width
Natividad González-Blanco, 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 Vertex-Monotone Fréchet Distance		 Stavros Kolliopoulos and Antonis Skarlatos:
Precedence-Constrained Covering Problems with Multiplicity Constraints		 Haozhe An, Mohit Jayanti Gurumukhani, Russell Impagliazzo, Michael Jaber, Marvin Künnemann and Maria Paula Parga Nina.
The fine-grained complexity of multi-dimensional 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 Gap-ETH
Vassilissa Lehoux-Lebacque and Christelle Loiodice:
Transfer customization with the Trip-Based 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üller-Hannemann		 IPEC Session 9
Niels Lindner, Pedro Maristany de Las Casas and Philine Schiewe:
Optimal Forks: Preprocessing Single-Source Shortest Path Instances with Interval Data		 Igor Razgon.
Classification of OBDD size for monotone 2-CNFs
Carlo S. Sartori, Pieter Smet and Greet Vanden Berghe:
Efficient duration-based 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

ALGOSENSORS 2021

International Symposium on Algorithms and Experiments for Wireless Sensor Networks, Sept. 9-10, 2021.
Chairs: Leszek Gąsieniec, Ralf Klasing, Tomasz Radzik


Location: ROOM 3. Please read [the instructions in this link] to get a better experience with the virtual conferences in ALGO 2021. Unsure about Portugal time zone? [Please check here].



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):
Universally-Optimal Distributed Algorithms, (Congestion+Dilation)-Competitive Oblivious Routing, and Hop-Constrained 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 unit-disk 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 Self-Eliminations
Abdullah Almethen, Othon Michail
and Igor Potapov:
Distributed Transformations of Hamiltonian Shapes
based on Line Moves
Matthew Connor, Othon Michail
and Igor Potapov:
Centralised Connectivity-Preserving 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 ell-p Unit Disks
in the Wireless Model
Nikos Leonardos, Aris Pagourtzis
and Ioannis Papaioannou:
Byzantine Fault Tolerant Symmetric-Persistent 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 Abstracts

Location: Auditorium. Unsure about Portugal time zone? [Please check here].


ALGOSENSORS Keynote (Thursday, Sept. 9, 13:00-14:15)
Universally-Optimal Distributed Algorithms, (Congestion+Dilation)- Competitive Oblivious Routing, and Hop-Constrained Network Design
Bernhard Haeupler, CMU, USA & ETHZ, SWITZERLAND
Many tasks on graphs/networks are optimizing either:
  • $\ell_1$ parameters like distances (e.g., computing short paths for low-delay communications),
  • $\ell_\infty$ parameters like congestion (e.g., computing maximum flows for high-rate communications), or,
  • $\ell_1$ both parameter types jointly (e.g., asking for short & low-congestion paths for minimizing the completion time of a communication task)
While ubiquitous, tasks of this joint type tend to be much harder and are less well understood. This talk presents new tools to address this. These tools were developed during a 6-year-long freshly-completed effort to obtain the first universally-optimal distributed graph algorithms (e.g., for MST, min-cut, SSSP, etc.). A universally-optimal algorithm is (approximately) as fast as the fastest algorithm for every graph topology. Other important results include:
  • The first Oblivious Routings that give short & low-congestion routes.
  • Fast distributed constructions of compact routing tables for such oblivious routings.
  • The first approximation and online algorithms for many diameter-constrained versions of classical network design problems (e.g., (group) Steiner Tree/Forest).
  • The first upper and lower bounds for how much (network) coding can speed up completion times of point-to-point network communications.
(joint work with M. Ghaffari, G. Zuzic, D. E. Hershkowitz, D. Wajc, J. Li, H. Raecke, T. Izumi)

ALGOSENSORS Session 1 (Thursday, Sept. 9, 14:15-15:30)
Distributed coloring and the local structure of unit-disk graphs
Louis Esperet, Sebastien Julliot and Arnaud de Mesmay
Coloring unit-disk graphs efficiently is an important problem in the global and distributed settings, with applications in radio channel assignment problems when the communication relies on omni-directional 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 location-aware setting (when nodes know their coordinates in the plane), we give a constant time distributed algorithm coloring any unit-disk 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 3-approximation algorithm for this problem, for all unit-disk 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 unit-disk 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 unit-disk graphs, which is of independent interest. We conjecture that every unit-disk graph $G$ has average degree at most $4\omega(G)$, which would imply the existence of a $O(\log n)$ round algorithm coloring any unit-disk graph $G$ with (approximatively) $4\omega(G)$ colors.

ALGOSENSORS Session 1 (Thursday, Sept. 9, 14:15-15:30)
Beep And Sleep: Message and Energy Efficient SetCover
Thorsten Götte, Christina Kolb, Christian Scheideler and Julian Werthmann.
We observe message- and energy-efficient 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:15-15: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 constant-storage agents such protocols can only compute predicates computable by immediate observation (IO) population protocols (sometimes also called one-way 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 message-based 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:45-17: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 crash-tolerant 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 semi-synchronous setting, we present the first solution to the problem for the fully synchronous setting that operates in the vanilla Look-Compute-Move 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:45-17: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 two-dimensional 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 so-called 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 non-isogonal configurations; it is based on the concept of runs using a constant number of lights.

ALGOSENSORS Session 3 (Friday, Sept. 10, 13:00-14:15)
Overflow Management with Self-Eliminations
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{self-elimination} 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 size-router capacity ratio. For real-world 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{tail-drop}. 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:00-14: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 two-dimensional square grid. Agents are equipped with a linear-strength 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 time-step. 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 connectivity-preserving transformation that exploits line moves within a total of $O(n \log_2 n)$ moves, which is asymptotically equivalent to that of the best-known 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:00-14:15)
Centralised Connectivity-Preserving 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 2-dimensional 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 3-node seed it is possible for the canonical shape of a line of $n$ nodes to be transformed into a nice shape of $n-1$ nodes. We use this to show that a 4-node 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:30-15:45)
Evacuating from ell-p Unit Disks in the Wireless Model
Konstantinos Georgiou, Sean Leizerovich, Jesse Lucier and Somnath Kundu
The search-type 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 follow-up results pertaining to variations as well as to upper and lower bound improvements. All established results in the area study this 2-dimensional search-type 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 search-type 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 two-fold. 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 trade-offs 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 non-extreme values of $p$.

ALGOSENSORS Session 4 (Friday, Sept. 10, 14:30-15:45)
Byzantine Fault Tolerant Symmetric-Persistent 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 symmetric-persistent 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 crash-faulty 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{2-4\sin(\frac{3\pi}{2n})+4 \sin^{2}{(\frac{3\pi}{2n})}}-2$.

ATMOS 2021

International Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, Sept. 9-10, 2021.
Chairs: Matthias Müller-Hannemann, Federico Perea Rojas-Marcos,.


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



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):
Universally-Optimal Distributed Algorithms, (Congestion+Dilation)-Competitive Oblivious Routing, and Hop-Constrained 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 non-periodic networks
15:30 break 15 min and posters session
15:45 ATMOS Session 2
Matthias Müller-Hannemann, Ralf Rückert, Alexander Schiewe and Anita Schöbel:
Towards Improved Robustness of Public Transport by a Machine-Learned Oracle
Syu-Ning Johnn, Yiran Zhu, Andrés Miniguano-Trujillo and Akshay Gupte:
Solving the Home Service Assignment, Routing, and Appointment scheduling (H-SARA) problem with Uncertainties
Daniela Gaul, Kathrin Klamroth and Michael Stiglmayr:
Solving the Dynamic Dial-a-Ride Problem Using a Rolling-Horizon Event-Based 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üller-Hannemann
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:
Distance-based Solution of Patrolling Problems with Individual Waiting Times
Marco Silva, Joao Pedro Pedroso, Ana Viana and Xenia Klimentova:
A branch-price-and-cut algorithm for stochastic crowd shipping last-mile 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 Multi-Period Line Planning Problem in Public Transportation (short paper)
Hector Gatt, Jean-Marie Freche, Fabien Lehuede and Thomas Yeung:
A column generation-based heuristic for the Line Planning Problem with Service Levels (short paper)
Natividad González-Blanco, 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 Vertex-Monotone 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 Lehoux-Lebacque and Christelle Loiodice:
Transfer customization with the Trip-Based Public Transit Routing Algorithm
18:30 break 15 min and posters session
18:45 ATMOS Session 7
chair: Matthias Müller-Hannemann
Niels Lindner, Pedro Maristany de Las Casas and Philine Schiewe:
Optimal Forks: Preprocessing Single-Source Shortest Path Instances with Interval Data
Carlo S. Sartori, Pieter Smet and Greet Vanden Berghe:
Efficient duration-based workload balancing for interdependent vehicle routes
19:35 end of the day


ATMOS Keynote

Location: Auditorium. Unsure about Portugal time zone? [Please check here].


ATMOS Keynote (Friday, Sept. 10, 16:00-17: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 real-world 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.

ESA 2021

European Symposium on Algorithms, Sept. 6-8, 2021.
Chairs: Rasmus Pagh (track A), Petra Mutzel (track B).


Location: ROOM 1, ROOM 2, ROOM 3. Please read [the instructions in this link] to get a better experience with the virtual conferences in ALGO 2021. Unsure about Portugal time zone? [Please check here].


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 3-coloring of small-diameter 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 t-matchings via half-edges		 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 two-dimensional 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 Scale-Free 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 4-edge-connected components in linear time 		Track B best student paper:
Florian Wörz and Jan-Hendrik Lorenz:
Evidence for Long-Tails in SLS Algorithms
Track A best paper:
Zhiyang He, Jason Li and Magnus Wahlström:
Near-linear-time, Optimal Vertex Cut Sparsifiers in Directed Acyclic Graphs
Track B best paper:
Simon D. Fink, Matthias Pfretzschner and Ignaz Rutter:
Experimental Comparison of PC-Trees and PQ-Trees
18:30 ESA Test-of-Time 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:
Space-efficient data structures
chair: Rasmus Pagh		 ESA Track A:
Parameterized algorithms
chair: Akanksha Agrawal
Saman Ahmadi, Guido Tack, Daniel Harabor and Philip Kilby:
Bi-objective Search with Bi-directional A*		 Moses Ganardi:
Compression by Contracting Straight-Line 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 Scale-Free 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:
Near-Optimal Deterministic Single-Source Distance Sensitivity Oracles		 Radu Curticapean, Holger Dell and Thore Husfeldt:
Modular counting of subgraphs: Matchings, matching-splittable 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:
On-line 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 n-Ellipses		 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 Instance-Robust 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 Sub-Gaussian 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 2-Local 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:
Worst-Case 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 Space-Efficient 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 Newton-Dinkelbach 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 Two-Dimensional Orthogonal Colored Range Counting		 Yishu Wang, Arnaud Mary, Marie-France 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 treewidth-fragile graphs		 Jean Cardinal, Justin Dallant and John Iacono:
An Instance-optimal 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:
k-Center Clustering with Outliers in the Sliding-Window Model
Timothy M. Chan:
All-Pairs Shortest Paths for Real-Weighted 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 max-flows and min-cuts in simplicial complexes		 Sariel Har-Peled 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 4-Edge-Connected Components of a Graph in Linear Time		 Alejandro Flores-Velazco and David Mount:
Boundary-Sensitive Approach for Approximate Nearest-Neighbor Classification		 David Caballero, Timothy Gomez, Robert Schweller and Tim Wylie:
Covert Computation in Staged Self-Assembly: Verification is PSPACE-complete
Karthekeyan Chandrasekaran and Weihang Wang:
ℓp-norm 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 Martinez-Munoz and Andreas Wiese:
FPT and FPT-approximation 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 Minor-hitting Sets		 Klaus Jansen and Malin Rau:
Closing the gap for single resource constraint scheduling
Joergen Bang-Jensen, Kristine Vitting Klinkby and Saket Saurabh:
k-Distinct 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

WAOA 2021

Workshop on Approximation and Online Algorithms, Sept. 9-10, 2021.
Chairs: Jochen Koenemann, Britta Peis.


Location: ROOM 2. Unsure about Portugal time zone? [Please check here].


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):
Universally-Optimal Distributed Algorithms, (Congestion+Dilation)-Competitive Oblivious Routing, and Hop-Constrained Network Design
14:00 break 15 min and posters session
14:15 WAOA Session 1
Waldo Gálvez, Francisco Sanhueza-Matamala and José A. Soto:
Approximation Algorithms for Vertex-Connectivity 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 b-Matchings and b-Edge Dominating Sets: A 2-Approximation Algorithm for the 4-Edge Dominating Set Problem
Dylan Huizing and Guido Schäfer:
The Traveling k-Median 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 Non-renewable 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:
Precedence-Constrained 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

Location: Auditorium. Unsure about Portugal time zone? [Please check here].


WAOA Keynote (Friday, Sept. 10, 17:15-18: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 un-obstructed path from the source to the destination.

IPEC 2021

International Symposium on Parameterized and Exact Computation, Sept. 8-10, 2021.
Chairs: Petr Golovach, Meirav Zehavi.


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


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 pattern-counting 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):
Universally-Optimal Distributed Algorithms, (Congestion+Dilation)-Competitive Oblivious Routing, and Hop-Constrained 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 clique-width
Guillaume Ducoffe.
Optimal centrality computations within bounded clique-width 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
Twin-width
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.
Twin-width and polynomial kernels
Jakub Balabán and Petr Hlineny.
Twin-Width 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 fine-grained complexity of multi-dimensional ordering properties
Akanksha Agrawal, Ravi Kiran Allumalla and Varun Teja Dhanekula.
FPT Algorithms for Some Parameterized Problems Under Gap-ETH/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 2-CNFs
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)

ALGOCLOUD 2021

International Symposium on Algorithmic Aspects of Cloud Computing, Sept. 6-7, 2021.
Chairs: Gianlorenzo D'Angelo, Othon Michail.


Location: ROOM 4 and Auditorium. Unsure about Portugal time zone? [Please check here].


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 Fault-Tolerant Online Bin Packing Problem
Léonard Lys, Arthur Micoulet and Maria Potop-Butucaru.
R-SWAP: Relay based atomic cross-chain 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:
Self-Adjusting 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:
Self-healing 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
Cloud-Assisted Peer-to-Peer Systems
14:15 break 15 min and posters session
14:30 Tutorial with Maria Potop-Butucaru:
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 Test-Cost 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

ALGOCLOUD Tutorials

Location: ROOM 4. Unsure about Portugal time zone? [Please check here].


Tutorial 1 (Monday, Sept. 6, 14:30-15:45)
Self-Adjusting Networks: Enablers, Algorithms, Complexity
Stefan Schmid, University of Vienna
Network traffic is growing explosively, and next-generation 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 wide-area 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 "self-adjusting" 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 demand-aware 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:15-18:30)
Self-healing Distributed Algorithms
 Amitabh Trehan, Durham University
Resilience and fault-tolerance are highly desirable properties for networks and often distributed algorithms are designed with this purpose in mind. Self-healing is one such fault-tolerance paradigm which seeks to maintain a desirable state of the system despite attack accepting only a short disruption. The concept of self-healing appears in various forms ranging from autonomic networks to practical networks to distributed algorithms. We look at the later setting formalising self-healing 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 P2P-CONGEST model (with limited message sizes). We look at various results in this setting building up self-healing resilience by adding topological properties such as connectivity, diameter, stretch, expansion, and routing in a simultaneous manner.

Tutorial 3 (Monday, Sept. 7, 14:30-15:45)
Gaming the Decentralized Finance
Maria Potop-Butucaru, , 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.