Portal - ESA 2023

ESA 2023	September 4-6, 2023, Amsterdam, The Netherlands
31st Annual European Symposium on Algorithms (ESA 2023) Inge Li Gørtz and Martin Farach-Colton and Simon J. Puglisi and Grzegorz Herman (Eds.)
ISBN 978-3-95977-295-2, LIPICS Vol. 274	ISSN 1868-8969

Additional Information

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

Authors

Bergougnoux, Benjamin

Brodal, Gerth Stølting

Da Cunha, Arthur Carvalho Walraven

Dietzfelbinger, Martin

Farach-Colton, Martin

Fonseca Faraj, Marcelo

Hébert-Johnson, Úrsula

Kanté, Mamadou Moustapha

Kipouridis, Evangelos

Klinkby, Kristine Vitting

Makarychev, Konstantin

Özüdoğru, Ahmet Alper

Sadigurschi, Menachem

Safier, Ron

Salavatipour, Mohammad R.

Sanders, Peter

Saranurak, Thatchaphol

Surianarayanan, Vaishali

van Leeuwen, Erik Jan

van Renssen, André

Vasilakis, Manolis

Vassilevska Williams, Virginia

Front Matter, Table of Contents, Preface, Conference Organization

Authors: Gørtz, Inge Li ; Farach-Colton, Martin ; Puglisi, Simon J. ; Herman, Grzegorz

Abstract | Document (533 KB) | BibTeX

On Hashing by (Random) Equations (Invited Talk)

Authors: Dietzfelbinger, Martin

Abstract | Document (393 KB) | BibTeX

On Diameter Approximation in Directed Graphs

Authors: Abboud, Amir ; Dalirrooyfard, Mina ; Li, Ray ; Vassilevska Williams, Virginia

Abstract | Document (894 KB) | BibTeX

Can You Solve Closest String Faster Than Exhaustive Search?

Authors: Abboud, Amir ; Fischer, Nick ; Goldenberg, Elazar ; Karthik C. S. ; Safier, Ron

Abstract | Document (696 KB) | BibTeX

What Else Can Voronoi Diagrams Do for Diameter in Planar Graphs?

Authors: Abboud, Amir ; Mozes, Shay ; Weimann, Oren

Abstract | Document (1,126 KB) | BibTeX

Smooth Distance Approximation

Authors: Abdelkader, Ahmed ; Mount, David M.

Abstract | Document (1,146 KB) | BibTeX

Reconfiguration of Polygonal Subdivisions via Recombination

Authors: A. Akitaya, Hugo ; Gonczi, Andrei ; Souvaine, Diane L. ; Tóth, Csaba D. ; Weighill, Thomas

Abstract | Document (1,718 KB) | BibTeX

Faster Detours in Undirected Graphs

Authors: Akmal, Shyan ; Vassilevska Williams, Virginia ; Williams, Ryan ; Xu, Zixuan

Abstract | Document (862 KB) | BibTeX

A Local-To-Global Theorem for Congested Shortest Paths

Authors: Akmal, Shyan ; Wein, Nicole

Abstract | Document (873 KB) | BibTeX

Axis-Parallel Right Angle Crossing Graphs

Authors: Angelini, Patrizio ; Bekos, Michael A. ; Katheder, Julia ; Kaufmann, Michael ; Pfister, Maximilian ; Ueckerdt, Torsten

Abstract | Document (1,162 KB) | BibTeX

(No) Quantum Space-Time Tradeoff for USTCON

Authors: Apers, Simon ; Jeffery, Stacey ; Pass, Galina ; Walter, Michael

Abstract | Document (922 KB) | BibTeX

Exploration of Graphs with Excluded Minors

Authors: Baligács, Júlia ; Disser, Yann ; Heinrich, Irene ; Schweitzer, Pascal

Abstract | Document (826 KB) | BibTeX

Learning-Augmented Online TSP on Rings, Trees, Flowers and (Almost) Everywhere Else

Authors: Bampis, Evripidis ; Escoffier, Bruno ; Gouleakis, Themis ; Hahn, Niklas ; Lakis, Kostas ; Shahkarami, Golnoosh ; Xefteris, Michalis

Abstract | Document (856 KB) | BibTeX

A Parameterized Algorithm for Vertex Connectivity Survivable Network Design Problem with Uniform Demands

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

Abstract | Document (868 KB) | BibTeX

Lyndon Arrays in Sublinear Time

Authors: Bannai, Hideo ; Ellert, Jonas

Abstract | Document (892 KB) | BibTeX

Sorting Finite Automata via Partition Refinement

Authors: Becker, Ruben ; Cáceres, Manuel ; Cenzato, Davide ; Kim, Sung-Hwan ; Kodric, Bojana ; Olivares, Francisco ; Prezza, Nicola

Abstract | Document (1,187 KB) | BibTeX

Fully Polynomial-Time Algorithms Parameterized by Vertex Integrity Using Fast Matrix Multiplication

Authors: Bentert, Matthias ; Heeger, Klaus ; Koana, Tomohiro

Abstract | Document (718 KB) | BibTeX

Approximating Min-Diameter: Standard and Bichromatic

Authors: Berger, Aaron ; Kaufmann, Jenny ; Vassilevska Williams, Virginia

Abstract | Document (854 KB) | BibTeX

Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth

Authors: Bergougnoux, Benjamin ; Chekan, Vera ; Ganian, Robert ; Kanté, Mamadou Moustapha ; Mnich, Matthias ; Oum, Sang-il ; Pilipczuk, Michał ; van Leeuwen, Erik Jan

Abstract | Document (1,817 KB) | BibTeX

High Performance Construction of RecSplit Based Minimal Perfect Hash Functions

Authors: Bez, Dominik ; Kurpicz, Florian ; Lehmann, Hans-Peter ; Sanders, Peter

Abstract | Document (914 KB) | BibTeX

On the Giant Component of Geometric Inhomogeneous Random Graphs

Authors: Bläsius, Thomas ; Friedrich, Tobias ; Katzmann, Maximilian ; Ruff, Janosch ; Zeif, Ziena

Abstract | Document (776 KB) | BibTeX

An Efficient Algorithm for Power Dominating Set

Authors: Bläsius, Thomas ; Göttlicher, Max

Abstract | Document (1,078 KB) | BibTeX

Incremental (1-ε)-Approximate Dynamic Matching in O(poly(1/ε)) Update Time

Authors: Blikstad, Joakim ; Kiss, Peter

Abstract | Document (940 KB) | BibTeX

Maximum Independent Set When Excluding an Induced Minor: K₁ + tK₂ and tC₃ ⊎ C₄

Authors: Bonnet, Édouard ; Duron, Julien ; Geniet, Colin ; Thomassé, Stéphan ; Wesolek, Alexandra

Abstract | Document (894 KB) | BibTeX

Faster 0-1-Knapsack via Near-Convex Min-Plus-Convolution

Authors: Bringmann, Karl ; Cassis, Alejandro

Abstract | Document (1,209 KB) | BibTeX

Funnelselect: Cache-Oblivious Multiple Selection

Authors: Brodal, Gerth Stølting ; Wild, Sebastian

Abstract | Document (907 KB) | BibTeX

Oriented Spanners

Authors: Buchin, Kevin ; Gudmundsson, Joachim ; Kalb, Antonia ; Popov, Aleksandr ; Rehs, Carolin ; van Renssen, André ; Wong, Sampson

Abstract | Document (822 KB) | BibTeX

Online Coalition Formation Under Random Arrival or Coalition Dissolution

Authors: Bullinger, Martin ; Romen, René

Abstract | Document (760 KB) | BibTeX

On k-Means for Segments and Polylines

Authors: Cabello, Sergio ; Giannopoulos, Panos

Abstract | Document (766 KB) | BibTeX

Effective Resistances in Non-Expander Graphs

Authors: Cai, Dongrun ; Chen, Xue ; Peng, Pan

Abstract | Document (897 KB) | BibTeX

New Menger-Like Dualities in Digraphs and Applications to Half-Integral Linkages

Authors: Campos, Victor ; Costa, Jonas ; Lopes, Raul ; Sau, Ignasi

Abstract | Document (870 KB) | BibTeX

Enumerating Maximal Induced Subgraphs

Authors: Cao, Yixin

Abstract | Document (698 KB) | BibTeX

Approximation Algorithm for Norm Multiway Cut

Authors: Carlson, Charlie ; Jafarov, Jafar ; Makarychev, Konstantin ; Makarychev, Yury ; Shan, Liren

Abstract | Document (660 KB) | BibTeX

Polynomial-Time Approximation of Independent Set Parameterized by Treewidth

Authors: Chalermsook, Parinya ; Fomin, Fedor ; Hamm, Thekla ; Korhonen, Tuukka ; Nederlof, Jesper ; Orgo, Ly

Abstract | Document (678 KB) | BibTeX

Faster Local Motif Clustering via Maximum Flows

Authors: Chhabra, Adil ; Fonseca Faraj, Marcelo ; Schulz, Christian

Abstract | Document (1,061 KB) | BibTeX

Primal-Dual Schemes for Online Matching in Bounded Degree Graphs

Authors: Cohen, Ilan Reuven ; Peng, Binghui

Abstract | Document (754 KB) | BibTeX

Robust and Space-Efficient Dual Adversary Quantum Query Algorithms

Authors: Czekanski, Michael ; Kimmel, Shelby ; Witter, R. Teal

Abstract | Document (782 KB) | BibTeX

Revisiting the Random Subset Sum Problem

Authors: Da Cunha, Arthur Carvalho Walraven ; d'Amore, Francesco ; Giroire, Frédéric ; Lesfari, Hicham ; Natale, Emanuele ; Viennot, Laurent

Abstract | Document (677 KB) | BibTeX

Scheduling with a Limited Testing Budget: Tight Results for the Offline and Oblivious Settings

Authors: Damerius, Christoph ; Kling, Peter ; Li, Minming ; Xu, Chenyang ; Zhang, Ruilong

Abstract | Document (1,169 KB) | BibTeX

A (3/2 + ε)-Approximation for Multiple TSP with a Variable Number of Depots

Authors: Deppert, Max ; Kaul, Matthias ; Mnich, Matthias

Abstract | Document (850 KB) | BibTeX

Efficient Parallel Output-Sensitive Edit Distance

Authors: Ding, Xiangyun ; Dong, Xiaojun ; Gu, Yan ; Liu, Youzhe ; Sun, Yihan

Abstract | Document (2,223 KB) | BibTeX

Efficient 1-Laplacian Solvers for Well-Shaped Simplicial Complexes: Beyond Betti Numbers and Collapsing Sequences

Authors: Ding, Ming ; Zhang, Peng

Abstract | Document (891 KB) | BibTeX

Optimal Energetic Paths for Electric Cars

Authors: Dorfman, Dani ; Kaplan, Haim ; Tarjan, Robert E. ; Zwick, Uri

Abstract | Document (841 KB) | BibTeX

Evaluating Restricted First-Order Counting Properties on Nowhere Dense Classes and Beyond

Authors: Dreier, Jan ; Mock, Daniel ; Rossmanith, Peter

Abstract | Document (801 KB) | BibTeX

Online Algorithms with Randomly Infused Advice

Authors: Emek, Yuval ; Gil, Yuval ; Pacut, Maciej ; Schmid, Stefan

Abstract | Document (793 KB) | BibTeX

The Lawn Mowing Problem: From Algebra to Algorithms

Authors: Fekete, Sándor P. ; Krupke, Dominik ; Perk, Michael ; Rieck, Christian ; Scheffer, Christian

Abstract | Document (1,286 KB) | BibTeX

Learned Monotone Minimal Perfect Hashing

Authors: Ferragina, Paolo ; Lehmann, Hans-Peter ; Sanders, Peter ; Vinciguerra, Giorgio

Abstract | Document (989 KB) | BibTeX

Correlating Theory and Practice in Finding Clubs and Plexes

Authors: Figiel, Aleksander ; Koana, Tomohiro ; Nichterlein, André ; Wünsche, Niklas

Abstract | Document (1,095 KB) | BibTeX

Kernelization for Spreading Points

Authors: Fomin, Fedor V. ; Golovach, Petr A. ; Inamdar, Tanmay ; Saurabh, Saket ; Zehavi, Meirav

Abstract | Document (977 KB) | BibTeX

Lossy Kernelization for (Implicit) Hitting Set Problems

Authors: Fomin, Fedor V. ; Le, Tien-Nam ; Lokshtanov, Daniel ; Saurabh, Saket ; Thomassé, Stéphan ; Zehavi, Meirav

Abstract | Document (855 KB) | BibTeX

Bootstrapping Dynamic Distance Oracles

Authors: Forster, Sebastian ; Goranci, Gramoz ; Nazari, Yasamin ; Skarlatos, Antonis

Abstract | Document (815 KB) | BibTeX

A Sweep-Plane Algorithm for Calculating the Isolation of Mountains

Authors: Funke, Daniel ; Hüning, Nicolai ; Sanders, Peter

Abstract | Document (4,942 KB) | BibTeX

A Tight Competitive Ratio for Online Submodular Welfare Maximization

Authors: Ganz, Amit ; Nuti, Pranav ; Schwartz, Roy

Abstract | Document (744 KB) | BibTeX

First Order Logic and Twin-Width in Tournaments

Authors: Geniet, Colin ; Thomassé, Stéphan

Abstract | Document (797 KB) | BibTeX

Improved Approximation Algorithms for the Expanding Search Problem

Authors: Griesbach, Svenja M. ; Hommelsheim, Felix ; Klimm, Max ; Schewior, Kevin

Abstract | Document (769 KB) | BibTeX

Noisy k-Means++ Revisited

Authors: Grunau, Christoph ; Özüdoğru, Ahmet Alper ; Rozhoň, Václav

Abstract | Document (659 KB) | BibTeX

Convergence to Lexicographically Optimal Base in a (Contra)Polymatroid and Applications to Densest Subgraph and Tree Packing

Authors: Harb, Elfarouk ; Quanrud, Kent ; Chekuri, Chandra

Abstract | Document (779 KB) | BibTeX

Algorithms for Matrix Multiplication via Sampling and Opportunistic Matrix Multiplication

Authors: Harris, David G.

Abstract | Document (699 KB) | BibTeX

Counting and Sampling Labeled Chordal Graphs in Polynomial Time

Authors: Hébert-Johnson, Úrsula ; Lokshtanov, Daniel ; Vigoda, Eric

Abstract | Document (809 KB) | BibTeX

Tight Algorithms for Connectivity Problems Parameterized by Clique-Width

Authors: Hegerfeld, Falko ; Kratsch, Stefan

Abstract | Document (950 KB) | BibTeX

Pareto Sums of Pareto Sets

Authors: Hespe, Demian ; Sanders, Peter ; Storandt, Sabine ; Truschel, Carina

Abstract | Document (1,503 KB) | BibTeX

Solving Edge Clique Cover Exactly via Synergistic Data Reduction

Authors: Hevia, Anthony ; Kallus, Benjamin ; McClintic, Summer ; Reisner, Samantha ; Strash, Darren ; Wilson, Johnathan

Abstract | Document (1,187 KB) | BibTeX

Threshold Testing and Semi-Online Prophet Inequalities

Authors: Hoefer, Martin ; Schewior, Kevin

Abstract | Document (753 KB) | BibTeX

Parameterized Complexity of Fair Bisection: (FPT-Approximation meets Unbreakability)

Authors: Inamdar, Tanmay ; Lokshtanov, Daniel ; Saurabh, Saket ; Surianarayanan, Vaishali

Abstract | Document (1,066 KB) | BibTeX

Improved Quantum Boosting

Authors: Izdebski, Adam ; de Wolf, Ronald

Abstract | Document (722 KB) | BibTeX

Finding Long Directed Cycles Is Hard Even When DFVS Is Small or Girth Is Large

Authors: Jacob, Ashwin ; Włodarczyk, Michał ; Zehavi, Meirav

Abstract | Document (6,698 KB) | BibTeX

5-Approximation for ℋ-Treewidth Essentially as Fast as ℋ-Deletion Parameterized by Solution Size

Authors: Jansen, Bart M. P. ; de Kroon, Jari J. H. ; Włodarczyk, Michał

Abstract | Document (970 KB) | BibTeX

The Unweighted and Weighted Reverse Shortest Path Problem for Disk Graphs

Authors: Kaplan, Haim ; Katz, Matthew J. ; Saban, Rachel ; Sharir, Micha

Abstract | Document (711 KB) | BibTeX

On Fully Dynamic Strongly Connected Components

Authors: Karczmarz, Adam ; Smulewicz, Marcin

Abstract | Document (716 KB) | BibTeX

An Improved Approximation Algorithm for the Max-3-Section Problem

Authors: Katzelnick, Dor ; Pillai, Aditya ; Schwartz, Roy ; Singh, Mohit

Abstract | Document (891 KB) | BibTeX

Fitting Tree Metrics with Minimum Disagreements

Authors: Kipouridis, Evangelos

Abstract | Document (654 KB) | BibTeX

Coloring Tournaments with Few Colors: Algorithms and Complexity

Authors: Klingelhoefer, Felix ; Newman, Alantha

Abstract | Document (685 KB) | BibTeX

Bellman-Ford Is Optimal for Shortest Hop-Bounded Paths

Authors: Kociumaka, Tomasz ; Polak, Adam

Abstract | Document (754 KB) | BibTeX

Towards Bypassing Lower Bounds for Graph Shortcuts

Authors: Kogan, Shimon ; Parter, Merav

Abstract | Document (808 KB) | BibTeX

Faster Block Tree Construction

Authors: Köppl, Dominik ; Kurpicz, Florian ; Meyer, Daniel

Abstract | Document (1,065 KB) | BibTeX

Connectivity Queries Under Vertex Failures: Not Optimal, but Practical

Authors: Kosinas, Evangelos

Abstract | Document (807 KB) | BibTeX

Improved Approximations for Translational Packing of Convex Polygons

Authors: Kurpisz, Adam ; Suter, Silvan

Abstract | Document (2,509 KB) | BibTeX

Structural Parameterizations for Two Bounded Degree Problems Revisited

Authors: Lampis, Michael ; Vasilakis, Manolis

Abstract | Document (813 KB) | BibTeX

Massively Parallel Algorithms for the Stochastic Block Model

Authors: Li, Zelin ; Peng, Pan ; Zhu, Xianbin

Abstract | Document (984 KB) | BibTeX

Connectivity in the Presence of an Opponent

Authors: Liang, Zihui ; Khoussainov, Bakh ; Takisaka, Toru ; Xiao, Mingyu

Abstract | Document (769 KB) | BibTeX

On the Perturbation Function of Ranking and Balance for Weighted Online Bipartite Matching

Authors: Liang, Jingxun ; Tang, Zhihao Gavin ; Xu, Yixuan Even ; Zhang, Yuhao ; Zhou, Renfei

Abstract | Document (989 KB) | BibTeX

Tight Bounds for Quantum Phase Estimation and Related Problems

Authors: Mande, Nikhil S. ; de Wolf, Ronald

Abstract | Document (811 KB) | BibTeX

A Fine-Grained Classification of the Complexity of Evaluating the Tutte Polynomial on Integer Points Parameterized by Treewidth and Cutwidth

Authors: Mannens, Isja ; Nederlof, Jesper

Abstract | Document (854 KB) | BibTeX

Matching Statistics Speed up BWT Construction

Authors: Masillo, Francesco

Abstract | Document (865 KB) | BibTeX

Approximation Schemes for Min-Sum k-Clustering

Authors: Naderi, Ismail ; Rezapour, Mohsen ; Salavatipour, Mohammad R.

Abstract | Document (1,324 KB) | BibTeX

Algorithms for Computing Maximum Cliques in Hyperbolic Random Graphs

Authors: Oh, Eunjin ; Oh, Seunghyeok

Abstract | Document (1,367 KB) | BibTeX

Parameterized Complexity of Equality MinCSP

Authors: Osipov, George ; Wahlström, Magnus

Abstract | Document (842 KB) | BibTeX

Engineering Fast Algorithms for the Bottleneck Matching Problem

Authors: Panagiotas, Ioannis ; Pichon, Grégoire ; Singh, Somesh ; Uçar, Bora

Abstract | Document (885 KB) | BibTeX

Subcubic Algorithm for (Unweighted) Unrooted Tree Edit Distance

Authors: Pióro, Krzysztof

Abstract | Document (700 KB) | BibTeX

Linear Time Construction of Cover Suffix Tree and Applications

Authors: Radoszewski, Jakub

Abstract | Document (841 KB) | BibTeX

Simultaneous Representation of Interval Graphs in the Sunflower Case

Authors: Rutter, Ignaz ; Stumpf, Peter

Abstract | Document (903 KB) | BibTeX

Relaxed Models for Adversarial Streaming: The Bounded Interruptions Model and the Advice Model

Authors: Sadigurschi, Menachem ; Shechner, Moshe ; Stemmer, Uri

Abstract | Document (768 KB) | BibTeX

Maximal k-Edge-Connected Subgraphs in Almost-Linear Time for Small k

Authors: Saranurak, Thatchaphol ; Yuan, Wuwei

Abstract | Document (744 KB) | BibTeX

Approximating Connected Maximum Cuts via Local Search

Authors: Schieber, Baruch ; Vahidi, Soroush

Abstract | Document (788 KB) | BibTeX

Parameterized Matroid-Constrained Maximum Coverage

Authors: Sellier, François

Abstract | Document (716 KB) | BibTeX

Fault Tolerance in Euclidean Committee Selection

Authors: Sonar, Chinmay ; Suri, Subhash ; Xue, Jie

Abstract | Document (806 KB) | BibTeX

Aggregating over Dominated Points by Sorting, Scanning, Zip and Flat Maps

Authors: Sroka, Jacek ; Tyszkiewicz, Jerzy

Abstract | Document (762 KB) | BibTeX

Improved Algorithms for Online Rent Minimization Problem Under Unit-Size Jobs

Authors: Sun, Enze ; Yang, Zonghan ; Zhang, Yuhao

Abstract | Document (749 KB) | BibTeX

Simple Deterministic Approximation for Submodular Multiple Knapsack Problem

Authors: Sun, Xiaoming ; Zhang, Jialin ; Zhang, Zhijie

Abstract | Document (753 KB) | BibTeX

The Tight Spanning Ratio of the Rectangle Delaunay Triangulation

Authors: van Renssen, André ; Sha, Yuan ; Sun, Yucheng ; Wong, Sampson

Abstract | Document (790 KB) | BibTeX

Canonization of a Random Graph by Two Matrix-Vector Multiplications

Authors: Verbitsky, Oleg ; Zhukovskii, Maksim

Abstract | Document (658 KB) | BibTeX

Improved Algorithms for Distance Selection and Related Problems

Authors: Wang, Haitao ; Zhao, Yiming

Abstract | Document (691 KB) | BibTeX

Maximum Coverage in Random-Arrival Streams

Authors: Warneke, Rowan ; Choudhury, Farhana ; Wirth, Anthony

Abstract | Document (828 KB) | BibTeX

Efficient Block Approximate Matrix Multiplication

Authors: Yang, Chuhan ; Musco, Christopher

Abstract | Document (3,166 KB) | BibTeX

A Simple Boosting Framework for Transshipment

Authors: Zuzic, Goran

Abstract | Document (871 KB) | BibTeX

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

31st Annual European Symposium on Algorithms (ESA 2023)