Portal - ESA 2021

ESA 2021	September 6-8, 2021, Lisbon, Portugal (Virtual Conference)
29th Annual European Symposium on Algorithms (ESA 2021) Petra Mutzel and Rasmus Pagh and Grzegorz Herman (Eds.)
ISBN 978-3-95977-204-4, LIPICS Vol. 204	ISSN 1868-8969

Additional Information

License
Conference Website
Complete volume (PDF, 44 MB)
Search Publication Server

Authors

Benkner, Louisa Seelbach

Chakrabarty, Deeparnab

Chan, Timothy M.

Chandrasekaran, Karthekeyan

Charalampopoulos, Panagiotis

Chen, Lin

Chiplunkar, Ashish

Cohen, Sarel

Colin de Verdière, Éric

de Lima, Murilo Santos

Eisenbrand, Friedrich

Fichtenberger, Hendrik

Fink, Simon D.

Fischer, Johannes

Flores-Velazco, Alejandro

Italiano, Giuseppe F.

Klinkby, Kristine Vitting

Koumoutsos, Grigorios

Král, Karel

Kulik, Ariel

Kulikov, Alexander S.

Martínez-Muñoz, Tomás

Naredla, Anurag Murty

Natura, Bento

Nayyeri, Amir

Neuen, Daniel

Nicholson, Patrick K.

Niklanovits, Aikaterini

Papadopoulou, Evanthia

Pfretzschner, Matthias

Ralbovsky, Peter Dominik

Schmidt genannt Waldschmidt, Daniel

Schrezenmaier, Hendrik

Wasylkiewicz, Mateusz

Front Matter, Table of Contents, Preface, Conference Organization

Authors: Mutzel, Petra ; Pagh, Rasmus ; Herman, Grzegorz

Abstract | Document (518 KB) | BibTeX

Network Planning and Routing Problems over Time: Models, Complexity and Algorithms (Invited Talk)

Authors: Glomb, Lukas ; Hoch, Benno ; Liers, Frauke ; Rösel, Florian

Abstract | Document (368 KB) | BibTeX

A User Friendly Power Tool for Deriving Online Learning Algorithms (Invited Talk)

Authors: Roth, Aaron

Abstract | Document (300 KB) | BibTeX

Bi-Objective Search with Bi-Directional A*

Authors: Ahmadi, Saman ; Tack, Guido ; Harabor, Daniel ; Kilby, Philip

Abstract | Document (1,286 KB) | BibTeX

A Unified Approach for All Pairs Approximate Shortest Paths in Weighted Undirected Graphs

Authors: Akav, Maor ; Roditty, Liam

Abstract | Document (782 KB) | BibTeX

The Voronoi Diagram of Rotating Rays With applications to Floodlight Illumination

Authors: Alegría, Carlos ; Mantas, Ioannis ; Papadopoulou, Evanthia ; Savić, Marko ; Schrezenmaier, Hendrik ; Seara, Carlos ; Suderland, Martin

Abstract | Document (1,660 KB) | BibTeX

Parallel Computation of Combinatorial Symmetries

Authors: Anders, Markus ; Schweitzer, Pascal

Abstract | Document (735 KB) | BibTeX

Graph Connectivity and Single Element Recovery via Linear and OR Queries

Authors: Assadi, Sepehr ; Chakrabarty, Deeparnab ; Khanna, Sanjeev

Abstract | Document (854 KB) | BibTeX

Fully Dynamic Set Cover via Hypergraph Maximal Matching: An Optimal Approximation Through a Local Approach

Authors: Assadi, Sepehr ; Solomon, Shay

Abstract | Document (766 KB) | BibTeX

The Randomized Competitive Ratio of Weighted k-Server Is at Least Exponential

Authors: Ayyadevara, Nikhil ; Chiplunkar, Ashish

Abstract | Document (661 KB) | BibTeX

Orienting (Hyper)graphs Under Explorable Stochastic Uncertainty

Authors: Bampis, Evripidis ; Dürr, Christoph ; Erlebach, Thomas ; de Lima, Murilo Santos ; Megow, Nicole ; Schlöter, Jens

Abstract | Document (853 KB) | BibTeX

k-Distinct Branchings Admits a Polynomial Kernel

Authors: Bang-Jensen, Jørgen ; Klinkby, Kristine Vitting ; Saurabh, Saket

Abstract | Document (940 KB) | BibTeX

Incremental Edge Orientation in Forests

Authors: Bender, Michael A. ; Kopelowitz, Tsvi ; Kuszmaul, William ; Porat, Ely ; Stein, Clifford

Abstract | Document (691 KB) | BibTeX

k-Center Clustering with Outliers in the Sliding-Window Model

Authors: de Berg, Mark ; Monemizadeh, Morteza ; Zhong, Yu

Abstract | Document (740 KB) | BibTeX

Incremental SCC Maintenance in Sparse Graphs

Authors: Bernstein, Aaron ; Dudeja, Aditi ; Pettie, Seth

Abstract | Document (909 KB) | BibTeX

Lyndon Words Accelerate Suffix Sorting

Authors: Bertram, Nico ; Ellert, Jonas ; Fischer, Johannes

Abstract | Document (1,108 KB) | BibTeX

Online Euclidean Spanners

Authors: Bhore, Sujoy ; Tóth, Csaba D.

Abstract | Document (1,041 KB) | BibTeX

Distant Representatives for Rectangles in the Plane

Authors: Biedl, Therese ; Lubiw, Anna ; Naredla, Anurag Murty ; Ralbovsky, Peter Dominik ; Stroud, Graeme

Abstract | Document (1,890 KB) | BibTeX

Near-Optimal Deterministic Single-Source Distance Sensitivity Oracles

Authors: Bilò, Davide ; Cohen, Sarel ; Friedrich, Tobias ; Schirneck, Martin

Abstract | Document (850 KB) | BibTeX

Synchronized Planarity with Applications to Constrained Planarity Problems

Authors: Bläsius, Thomas ; Fink, Simon D. ; Rutter, Ignaz

Abstract | Document (934 KB) | BibTeX

Efficiently Approximating Vertex Cover on Scale-Free Networks with Underlying Hyperbolic Geometry

Authors: Bläsius, Thomas ; Friedrich, Tobias ; Katzmann, Maximilian

Abstract | Document (952 KB) | BibTeX

Efficiently Computing Maximum Flows in Scale-Free Networks

Authors: Bläsius, Thomas ; Friedrich, Tobias ; Weyand, Christopher

Abstract | Document (750 KB) | BibTeX

Asymptotically Optimal Welfare of Posted Pricing for Multiple Items with MHR Distributions

Authors: Braun, Alexander ; Buttkus, Matthias ; Kesselheim, Thomas

Abstract | Document (678 KB) | BibTeX

Covert Computation in Staged Self-Assembly: Verification Is PSPACE-Complete

Authors: Caballero, David ; Gomez, Timothy ; Schweller, Robert ; Wylie, Tim

Abstract | Document (1,366 KB) | BibTeX

An Instance-Optimal Algorithm for Bichromatic Rectangular Visibility

Authors: Cardinal, Jean ; Dallant, Justin ; Iacono, John

Abstract | Document (849 KB) | BibTeX

Worst-Case Efficient Dynamic Geometric Independent Set

Authors: Cardinal, Jean ; Iacono, John ; Koumoutsos, Grigorios

Abstract | Document (721 KB) | BibTeX

Balanced Crown Decomposition for Connectivity Constraints

Authors: Casel, Katrin ; Friedrich, Tobias ; Issac, Davis ; Niklanovits, Aikaterini ; Zeif, Ziena

Abstract | Document (843 KB) | BibTeX

All-Pairs Shortest Paths for Real-Weighted Undirected Graphs with Small Additive Error

Authors: Chan, Timothy M.

Abstract | Document (669 KB) | BibTeX

Dynamic Colored Orthogonal Range Searching

Authors: Chan, Timothy M. ; Huang, Zhengcheng

Abstract | Document (678 KB) | BibTeX

𝓁_p-Norm Multiway Cut

Authors: Chandrasekaran, Karthekeyan ; Wang, Weihang

Abstract | Document (859 KB) | BibTeX

Faster Algorithms for Longest Common Substring

Authors: Charalampopoulos, Panagiotis ; Kociumaka, Tomasz ; Pissis, Solon P. ; Radoszewski, Jakub

Abstract | Document (968 KB) | BibTeX

Feature Cross Search via Submodular Optimization

Authors: Chen, Lin ; Esfandiari, Hossein ; Fu, Gang ; Mirrokni, Vahab S. ; Yu, Qian

Abstract | Document (740 KB) | BibTeX

An FPT Algorithm for the Embeddability of Graphs into Two-Dimensional Simplicial Complexes

Authors: Colin de Verdière, Éric ; Magnard, Thomas

Abstract | Document (749 KB) | BibTeX

Efficient Sequential and Parallel Algorithms for Multistage Stochastic Integer Programming Using Proximity

Authors: Cslovjecsek, Jana ; Eisenbrand, Friedrich ; Pilipczuk, Michał ; Venzin, Moritz ; Weismantel, Robert

Abstract | Document (770 KB) | BibTeX

Modular Counting of Subgraphs: Matchings, Matching-Splittable Graphs, and Paths

Authors: Curticapean, Radu ; Dell, Holger ; Husfeldt, Thore

Abstract | Document (884 KB) | BibTeX

Minimum Common String Partition: Exact Algorithms

Authors: Cygan, Marek ; Kulikov, Alexander S. ; Mihajlin, Ivan ; Nikolaev, Maksim ; Reznikov, Grigory

Abstract | Document (736 KB) | BibTeX

An Accelerated Newton-Dinkelbach Method and Its Application to Two Variables per Inequality Systems

Authors: Dadush, Daniel ; Koh, Zhuan Khye ; Natura, Bento ; Végh, László A.

Abstract | Document (814 KB) | BibTeX

Faster 3-Coloring of Small-Diameter Graphs

Authors: Dębski, Michał ; Piecyk, Marta ; Rzążewski, Paweł

Abstract | Document (930 KB) | BibTeX

Stability Yields Sublinear Time Algorithms for Geometric Optimization in Machine Learning

Authors: Ding, Hu

Abstract | Document (945 KB) | BibTeX

Data Structures Lower Bounds and Popular Conjectures

Authors: Dvořák, Pavel ; Koucký, Michal ; Král, Karel ; Slívová, Veronika

Abstract | Document (806 KB) | BibTeX

Approximation Schemes for Bounded Distance Problems on Fractionally Treewidth-Fragile Graphs

Authors: Dvořák, Zdeněk ; Lahiri, Abhiruk

Abstract | Document (666 KB) | BibTeX

Modular and Submodular Optimization with Multiple Knapsack Constraints via Fractional Grouping

Authors: Fairstein, Yaron ; Kulik, Ariel ; Shachnai, Hadas

Abstract | Document (771 KB) | BibTeX

Differentially Private Algorithms for Graphs Under Continual Observation

Authors: Fichtenberger, Hendrik ; Henzinger, Monika ; Ost, Wolfgang

Abstract | Document (797 KB) | BibTeX

Experimental Comparison of PC-Trees and PQ-Trees

Authors: Fink, Simon D. ; Pfretzschner, Matthias ; Rutter, Ignaz

Abstract | Document (10,590 KB) | BibTeX

Boundary-Sensitive Approach for Approximate Nearest-Neighbor Classification

Authors: Flores-Velazco, Alejandro ; Mount, David M.

Abstract | Document (1,289 KB) | BibTeX

Compression by Contracting Straight-Line Programs

Authors: Ganardi, Moses

Abstract | Document (802 KB) | BibTeX

Space Efficient Two-Dimensional Orthogonal Colored Range Counting

Authors: Gao, Younan ; He, Meng

Abstract | Document (720 KB) | BibTeX

Computing the 4-Edge-Connected Components of a Graph in Linear Time

Authors: Georgiadis, Loukas ; Italiano, Giuseppe F. ; Kosinas, Evangelos

Abstract | Document (811 KB) | BibTeX

Deep Multilevel Graph Partitioning

Authors: Gottesbüren, Lars ; Heuer, Tobias ; Sanders, Peter ; Schulz, Christian ; Seemaier, Daniel

Abstract | Document (1,628 KB) | BibTeX

Faster (1+ε)-Approximation for Unsplittable Flow on a Path via Resource Augmentation and Back

Authors: Grandoni, Fabrizio ; Mömke, Tobias ; Wiese, Andreas

Abstract | Document (775 KB) | BibTeX

Quantum Sub-Gaussian Mean Estimator

Authors: Hamoudi, Yassine

Abstract | Document (785 KB) | BibTeX

Improved Approximation Algorithms for Tverberg Partitions

Authors: Har-Peled, Sariel ; Zhou, Timothy

Abstract | Document (900 KB) | BibTeX

Near-Linear-Time, Optimal Vertex Cut Sparsifiers in Directed Acyclic Graphs

Authors: He, Zhiyang ; Li, Jason ; Wahlström, Magnus

Abstract | Document (807 KB) | BibTeX

Closing the Gap for Single Resource Constraint Scheduling

Authors: Jansen, Klaus ; Rau, Malin

Abstract | Document (828 KB) | BibTeX

Certified Approximation Algorithms for the Fermat Point and n-Ellipses

Authors: Junginger, Kolja ; Mantas, Ioannis ; Papadopoulou, Evanthia ; Suderland, Martin ; Yap, Chee

Abstract | Document (4,119 KB) | BibTeX

Parameterized Algorithms for Diverse Multistage Problems

Authors: Kellerhals, Leon ; Renken, Malte ; Zschoche, Philipp

Abstract | Document (857 KB) | BibTeX

Fast and Space-Efficient Construction of AVL Grammars from the LZ77 Parsing

Authors: Kempa, Dominik ; Langmead, Ben

Abstract | Document (809 KB) | BibTeX

Convex Drawings of Hierarchical Graphs in Linear Time, with Applications to Planar Graph Morphing

Authors: Klemz, Boris

Abstract | Document (1,391 KB) | BibTeX

QCSP on Reflexive Tournaments

Authors: Larose, Benoît ; Marković, Petar ; Martin, Barnaby ; Paulusma, Daniël ; Smith, Siani ; Živný, Stanislav

Abstract | Document (741 KB) | BibTeX

Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancing

Authors: Lavastida, Thomas ; Moseley, Benjamin ; Ravi, R. ; Xu, Chenyang

Abstract | Document (745 KB) | BibTeX

Telescoping Filter: A Practical Adaptive Filter

Authors: Lee, David J. ; McCauley, Samuel ; Singh, Shikha ; Stein, Max

Abstract | Document (1,344 KB) | BibTeX

Finding an Approximate Mode of a Kernel Density Estimate

Authors: Lee, Jasper C.H. ; Li, Jerry ; Musco, Christopher ; Phillips, Jeff M. ; Tai, Wai Ming

Abstract | Document (793 KB) | BibTeX

An Efficient Reduction of a Gammoid to a Partition Matroid

Authors: Leichter, Marilena ; Moseley, Benjamin ; Pruhs, Kirk

Abstract | Document (826 KB) | BibTeX

Efficient Algorithms for Least Square Piecewise Polynomial Regression

Authors: Lokshtanov, Daniel ; Suri, Subhash ; Xue, Jie

Abstract | Document (777 KB) | BibTeX

Bidirectional String Anchors: A New String Sampling Mechanism

Authors: Loukides, Grigorios ; Pissis, Solon P.

Abstract | Document (1,342 KB) | BibTeX

The Visibility Center of a Simple Polygon

Authors: Lubiw, Anna ; Naredla, Anurag Murty

Abstract | Document (1,782 KB) | BibTeX

Extension of Additive Valuations to General Valuations on the Existence of EFX

Authors: Mahara, Ryoga

Abstract | Document (723 KB) | BibTeX

FPT and FPT-Approximation Algorithms for Unsplittable Flow on Trees

Authors: Martínez-Muñoz, Tomás ; Wiese, Andreas

Abstract | Document (785 KB) | BibTeX

A Simple Algorithm for Graph Reconstruction

Authors: Mathieu, Claire ; Zhou, Hang

Abstract | Document (942 KB) | BibTeX

Generalized Max-Flows and Min-Cuts in Simplicial Complexes

Authors: Maxwell, William ; Nayyeri, Amir

Abstract | Document (706 KB) | BibTeX

Hypersuccinct Trees - New Universal Tree Source Codes for Optimal Compressed Tree Data Structures and Range Minima

Authors: Munro, J. Ian ; Nicholson, Patrick K. ; Benkner, Louisa Seelbach ; Wild, Sebastian

Abstract | Document (939 KB) | BibTeX

Determining 4-Edge-Connected Components in Linear Time

Authors: Nadara, Wojciech ; Radecki, Mateusz ; Smulewicz, Marcin ; Sokołowski, Marek

Abstract | Document (662 KB) | BibTeX

Isomorphism Testing Parameterized by Genus and Beyond

Authors: Neuen, Daniel

Abstract | Document (779 KB) | BibTeX

Restricted t-Matchings via Half-Edges

Authors: Paluch, Katarzyna ; Wasylkiewicz, Mateusz

Abstract | Document (736 KB) | BibTeX

Beating Random Assignment for Approximating Quantum 2-Local Hamiltonian Problems

Authors: Parekh, Ojas ; Thompson, Kevin

Abstract | Document (790 KB) | BibTeX

Additive Sparsification of CSPs

Authors: Pelleg, Eden ; Živný, Stanislav

Abstract | Document (798 KB) | BibTeX

Faster Deterministic Modular Subset Sum

Authors: Potępa, Krzysztof

Abstract | Document (677 KB) | BibTeX

Hardness of Detecting Abelian and Additive Square Factors in Strings

Authors: Radoszewski, Jakub ; Rytter, Wojciech ; Straszyński, Juliusz ; Waleń, Tomasz ; Zuba, Wiktor

Abstract | Document (1,007 KB) | BibTeX

On Approximate Compressions for Connected Minor-Hitting Sets

Authors: Ramanujan, M. S.

Abstract | Document (833 KB) | BibTeX

Restricted Adaptivity in Stochastic Scheduling

Authors: Sagnol, Guillaume ; Schmidt genannt Waldschmidt, Daniel

Abstract | Document (931 KB) | BibTeX

A General Framework for Enumerating Equivalence Classes of Solutions

Authors: Wang, Yishu ; Mary, Arnaud ; Sagot, Marie-France ; Sinaimeri, Blerina

Abstract | Document (749 KB) | BibTeX

Engineering MultiQueues: Fast Relaxed Concurrent Priority Queues

Authors: Williams, Marvin ; Sanders, Peter ; Dementiev, Roman

Abstract | Document (1,439 KB) | BibTeX

Evidence for Long-Tails in SLS Algorithms

Authors: Wörz, Florian ; Lorenz, Jan-Hendrik

Abstract | Document (1,483 KB) | BibTeX

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI

29th Annual European Symposium on Algorithms (ESA 2021)