ESA 2021 Accepted Papers
Sariel Har-Peled and Timothy Zhou. Improved Approximation Algorithms for Tverberg Partitions
Michał Dębski, Marta Piecyk and Paweł Rzążewski. Faster 3-coloring of small-diameter graphs Sepehr Assadi, Deeparnab Chakrabarty and Sanjeev Khanna. Graph Connectivity and Single Element Recovery via Linear and OR Queries Lars Gottesbüren, Tobias Heuer, Peter Sanders, Christian Schulz and Daniel Seemaier. Deep Multilevel Graph Partitioning Markus Anders and Pascal Schweitzer. Parallel Computation of Combinatorial Symmetries
Florian Wörz and Jan-Hendrik Lorenz. Evidence for Long-Tails in SLS Algorithms
Nikhil Ayyadevara and Ashish Chiplunkar. The Randomized Competitive Ratio of Weighted $k$-Server is at Least Exponential Ryoga Mahara. Extension of Additive Valuations to General Valuations on the Existence of EFX
Grigorios Loukides and Solon Pissis. Bidirectional String Anchors: a New String Sampling Mechanism Hendrik Fichtenberger, Monika Henzinger and Wolfgang Ost. Differentially Private Algorithms for Graphs Under Continual Observation
Hu Ding. Stability Yields Sublinear Time Algorithms for Geometric Optimization in Machine Learning
Tomas Martinez-Munoz and Andreas Wiese. FPT and FPT-approximation algorithms for Unsplittable Flow on Trees
Krzysztof Potępa. Faster Deterministic Modular Subset Sum
Maor Akav and Liam Roditty. A unified approach for all pairs approximate shortest paths in weighted undirected graphs
Aaron Bernstein, Aditi Dudeja and Seth Pettie. Incremental SCC Maintenance in Sparse Graphs
Timothy M. Chan and Zhengcheng Huang. Dynamic Colored Orthogonal Range Searching Timothy M. Chan. All-Pairs Shortest Paths for Real-Weighted Undirected Graphs with Small Additive Error Éric Colin de Verdière and Thomas Magnard. An FPT algorithm for the embeddability of graphs into two-dimensional simplicial complexes Thomas Bläsius, Tobias Friedrich and Christopher Weyand. Efficiently Computing Maximum Flows in Scale-Free Networks
Zdenek Dvorak and Abhiruk Lahiri. Approximation schemes for bounded distance problems on fractionally treewidth-fragile graphs Davide Bilò, Sarel Cohen, Tobias Friedrich and Martin Schirneck. Near-Optimal Deterministic Single-Source Distance Sensitivity Oracles
Marilena Leichter, Benjamin Moseley and Kirk Pruhs. An Efficient Reduction of a Gammoid to a Partition Matroid
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 William Maxwell and Amir Nayyeri. Generalized max-flows and min-cuts in simplicial complexes
Evripidis Bampis, Christoph Dürr, Thomas Erlebach, Murilo S. de Lima, Nicole Megow and Jens Schlöter. Orienting (hyper)graphs under explorable stochastic uncertainty
Klaus Jansen and Malin Rau. Closing the gap for single resource constraint scheduling Sujoy Bhore and Csaba Toth. Online Euclidean Spanners Daniel Neuen. Isomorphism Testing Parameterized by Genus and Beyond
Pavel Dvořák, Michal Koucký, Karel Král and Veronika Slívová. Data Structures Lower Bounds and Popular Conjectures
Lin Chen, Hossein Esfandiari, Thomas Fu, Vahab Mirrokni and Qian Yu. Feature Cross Search via Submodular Optimization
Yaron Fairstein, Ariel Kulik and Hadas Shachnai. Modular and Submodular Optimization with Multiple Knapsack Constraints via Fractional Grouping
Kolja Junginger, Ioannis Mantas, Evanthia Papadopoulou, Martin Suderland and Chee Yap. Certified Approximation Algorithms for the Fermat Point and n-Ellipses
Fabrizio Grandoni, Tobias Mömke and Andreas Wiese. Faster (1+epsilon)-approximation for Unsplittable Flow on a Path via resource augmentation and back Zhiyang He, Jason Li and Magnus Wahlström. Near-linear-time, Optimal Vertex Cut Sparsifiers in Directed Acyclic Graphs
Marek Cygan, Alexander Kulikov, Ivan Mihajlin, Maksim Nikolaev and Grigory Reznikov. Minimum Common String Partition: Exact Algorithms Evangelos Kosinas, Loukas Georgiadis and Giuseppe F. Italiano. Computing the 4-Edge-Connected Components of a Graph in Linear Time Thomas Lavastida, Benjamin Moseley, R. Ravi and Chenyang Xu. Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancing Guillaume Sagnol and Daniel Schmidt Genannt Waldschmidt. Restricted Adaptivity in Stochastic Scheduling
David Caballero, Timothy Gomez, Robert Schweller and Tim Wylie. Covert Computation in Staged Self-Assembly: Verification is PSPACE-complete Therese Biedl, Anna Lubiw, Anurag Murty Naredla, Peter Dominik Ralbovsky and Graeme Stroud. Distant Representatives for Rectangles in the Plane Anna Lubiw and Anurag Murty Naredla. The Visibility Center of a Simple Polygon Leon Kellerhals, Malte Renken and Philipp Zschoche. Parameterized Algorithms for Diverse Multistage Problems Ojas Parekh and Kevin Thompson. Beating Random Assignment for Approximating Quantum 2-Local Hamiltonian Problems
Boris Klemz. Convex drawings of hierarchical graphs in linear time, with applications to planar graph morphing Katrin Casel, Tobias Friedrich, Davis Issac, Aikaterini Niklanovits and Ziena Zeif. Balanced Crown Decomposition for Connectivity Constraints
Katarzyna Paluch and Mateusz Wasylkiewicz. Restricted t-matchings via half-edges David Lee, Samuel McCauley, Shikha Singh and Max Stein. Telescoping Filter: A Practical Adaptive Filter Younan Gao and Meng He. Space Efficient Two-Dimensional Orthogonal Colored Range Counting Sepehr Assadi and Shay Solomon. Fully Dynamic Set Cover via Hypergraph Maximal Matching: An Optimal Approximation Through a Local Approach Jana Cslovjecsek, Friedrich Eisenbrand, Michał Pilipczuk, Moritz Venzin and Robert Weismantel. Efficient sequential and parallel algorithms for multistage stochastic integer programming using proximity Peter Sanders, Marvin Williams and Roman Dementiev. Engineering MultiQueues: Fast Relaxed Concurrent Priority Queues Wojciech Nadara, Mateusz Radecki, Marcin Smulewicz and Marek Sokołowski. Determining 4-edge-connected components in linear time