LIPIcs, Volume 274, ESA 2023, Complete Volume (English)
Free access
- New search for: Gørtz, Inge Li
- Further information on Gørtz, Inge Li:
- https://orcid.org/0000-0002-8322-4952
- New search for: Farach-Colton, Martin
- Further information on Farach-Colton, Martin:
- https://orcid.org/0000-0003-3616-7788
- New search for: Puglisi, Simon J.
- Further information on Puglisi, Simon J.:
- https://orcid.org/0000-0001-7668-7636
- New search for: Herman, Grzegorz
- Further information on Herman, Grzegorz:
- https://orcid.org/0000-0001-6855-8316
- New search for: Gørtz, Inge Li
- Further information on Gørtz, Inge Li:
- https://orcid.org/0000-0002-8322-4952
- New search for: Farach-Colton, Martin
- Further information on Farach-Colton, Martin:
- https://orcid.org/0000-0003-3616-7788
- New search for: Puglisi, Simon J.
- Further information on Puglisi, Simon J.:
- https://orcid.org/0000-0001-7668-7636
- New search for: Herman, Grzegorz
- Further information on Herman, Grzegorz:
- https://orcid.org/0000-0001-6855-8316
2023
-
ISBN:
-
ISSN:
- Conference Proceedings / Electronic Resource
-
Title:LIPIcs, Volume 274, ESA 2023, Complete Volume
-
Contributors:Gørtz, Inge Li ( author , editor ) / Farach-Colton, Martin ( author , editor ) / Puglisi, Simon J. ( author , editor ) / Herman, Grzegorz ( author , editor )
-
Published in:
-
Publisher:
- New search for: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
-
Publication date:2023-08-30
-
Size:1700 pages , 40754002 byte
-
Remarks:LIPIcs, Vol. 274, 31st Annual European Symposium on Algorithms (ESA 2023), pages 1-1700
-
ISBN:
-
ISSN:
-
DOI:
-
Type of media:Conference Proceedings
-
Type of material:Electronic Resource
-
Language:English
-
Keywords:Theory of computation → Facility location and clustering , Mathematics of computing → Graph theory , Theory of computation → Computational geometry , Theory of computation → Massively parallel algorithms , Theory of computation → Randomness, geometry and discrete structures , Theory of computation → Mixed discrete-continuous optimization , Theory of computation → Computational complexity and cryptography , Social and professional topics → Social engineering attacks , Theory of computation → Generating random combinatorial structures , Theory of computation → Sparsification and spanners , Mathematics of computing → Paths and connectivity problems , Theory of computation → Packing and covering problems , Computing methodologies → Machine learning , Theory of computation → Logic and verification , Mathematics of computing → Combinatorial algorithms , Theory of computation → Semidefinite programming , Theory of computation → Database query processing and optimization (theory) , Theory of computation → Oracles and decision trees , Mathematics of computing → Graphs and surfaces , Mathematics of computing → Combinatoric problems , Theory of computation → Algorithm design techniques , Theory of computation → Data compression , Theory of computation → Pattern matching , Theory of computation → Parallel algorithms , Theory of computation → Sorting and searching , Theory of computation → Parameterized complexity and exact algorithms , Mathematics of computing → Random graphs , Mathematics of computing → Computations on matrices , Theory of computation → Parallel computing models , Theory of computation → Online algorithms , Theory of computation → Fixed parameter tractability , Theory of computation → Scheduling algorithms , Theory of computation → Unsupervised learning and clustering , Theory of computation → Design and analysis of algorithms , Mathematics of computing → Graph enumeration , Mathematics of computing → Stochastic processes , Theory of computation → Quantum query complexity , Theory of computation → Complexity theory and logic , Theory of computation → Finite Model Theory , Theory of computation → Theory and algorithms for application domains , Mathematics of computing → Algebraic topology , Theory of computation → Markov decision processes , Theory of computation → Quantum computation theory , Theory of computation → Sketching and sampling , Theory of computation → Approximation algorithms analysis , Theory of computation → Algorithmic game theory , Theory of computation → Random order and robust communication complexity , Theory of computation → Streaming, sublinear and near linear time algorithms , Mathematics of computing → Approximation algorithms , Theory of computation → Problems, reductions and completeness , Information systems → Point lookups , Mathematics of computing → Matchings and factors , LIPIcs, Volume 274, ESA 2023, Complete Volume , Theory of computation → Graph algorithms analysis , Theory of computation → Random network models , Theory of computation → Mathematical optimization , Theory of computation → Nonconvex optimization , Theory of computation → Dynamic graph algorithms , Theory of computation → Random projections and metric embeddings , Mathematics of computing → Graph algorithms , Theory of computation → Shortest paths
-
Licence:
-
Source:
Table of contents conference proceedings
The tables of contents are generated automatically and are based on the data records of the individual contributions available in the index of the TIB portal. The display of the Tables of Contents may therefore be incomplete.
- 1
-
On Hashing by (Random) Equations (Invited Talk)Dietzfelbinger, Martin et al. | 2023
- 2
-
On Diameter Approximation in Directed GraphsAbboud, Amir / Dalirrooyfard, Mina / Li, Ray / Vassilevska Williams, Virginia et al. | 2023
- 3
-
Can You Solve Closest String Faster Than Exhaustive Search?Abboud, Amir / Fischer, Nick / Goldenberg, Elazar / Karthik C. S. / Safier, Ron et al. | 2023
- 4
-
What Else Can Voronoi Diagrams Do for Diameter in Planar Graphs?Abboud, Amir / Mozes, Shay / Weimann, Oren et al. | 2023
- 5
-
Smooth Distance ApproximationAbdelkader, Ahmed / Mount, David M. et al. | 2023
- 6
-
Reconfiguration of Polygonal Subdivisions via RecombinationA. Akitaya, Hugo / Gonczi, Andrei / Souvaine, Diane L. / Tóth, Csaba D. / Weighill, Thomas et al. | 2023
- 7
-
Faster Detours in Undirected GraphsAkmal, Shyan / Vassilevska Williams, Virginia / Williams, Ryan / Xu, Zixuan et al. | 2023
- 8
-
A Local-To-Global Theorem for Congested Shortest PathsAkmal, Shyan / Wein, Nicole et al. | 2023
- 9
-
Axis-Parallel Right Angle Crossing GraphsAngelini, Patrizio / Bekos, Michael A. / Katheder, Julia / Kaufmann, Michael / Pfister, Maximilian / Ueckerdt, Torsten et al. | 2023
- 10
-
(No) Quantum Space-Time Tradeoff for USTCONApers, Simon / Jeffery, Stacey / Pass, Galina / Walter, Michael et al. | 2023
- 11
-
Exploration of Graphs with Excluded MinorsBaligács, Júlia / Disser, Yann / Heinrich, Irene / Schweitzer, Pascal et al. | 2023
- 12
-
Learning-Augmented Online TSP on Rings, Trees, Flowers and (Almost) Everywhere ElseBampis, Evripidis / Escoffier, Bruno / Gouleakis, Themis / Hahn, Niklas / Lakis, Kostas / Shahkarami, Golnoosh / Xefteris, Michalis et al. | 2023
- 13
-
A Parameterized Algorithm for Vertex Connectivity Survivable Network Design Problem with Uniform DemandsBang-Jensen, Jørgen / Klinkby, Kristine Vitting / Misra, Pranabendu / Saurabh, Saket et al. | 2023
- 14
-
Lyndon Arrays in Sublinear TimeBannai, Hideo / Ellert, Jonas et al. | 2023
- 15
-
Sorting Finite Automata via Partition RefinementBecker, Ruben / Cáceres, Manuel / Cenzato, Davide / Kim, Sung-Hwan / Kodric, Bojana / Olivares, Francisco / Prezza, Nicola et al. | 2023
- 16
-
Fully Polynomial-Time Algorithms Parameterized by Vertex Integrity Using Fast Matrix MultiplicationBentert, Matthias / Heeger, Klaus / Koana, Tomohiro et al. | 2023
- 17
-
Approximating Min-Diameter: Standard and BichromaticBerger, Aaron / Kaufmann, Jenny / Vassilevska Williams, Virginia et al. | 2023
- 18
-
Space-Efficient Parameterized Algorithms on Graphs of Low ShrubdepthBergougnoux, Benjamin / Chekan, Vera / Ganian, Robert / Kanté, Mamadou Moustapha / Mnich, Matthias / Oum, Sang-il / Pilipczuk, Michał / van Leeuwen, Erik Jan et al. | 2023
- 19
-
High Performance Construction of RecSplit Based Minimal Perfect Hash FunctionsBez, Dominik / Kurpicz, Florian / Lehmann, Hans-Peter / Sanders, Peter et al. | 2023
- 20
-
On the Giant Component of Geometric Inhomogeneous Random GraphsBläsius, Thomas / Friedrich, Tobias / Katzmann, Maximilian / Ruff, Janosch / Zeif, Ziena et al. | 2023
- 21
-
An Efficient Algorithm for Power Dominating SetBläsius, Thomas / Göttlicher, Max et al. | 2023
- 22
-
Incremental (1-ε)-Approximate Dynamic Matching in O(poly(1/ε)) Update TimeBlikstad, Joakim / Kiss, Peter et al. | 2023
- 23
-
Maximum Independent Set When Excluding an Induced Minor: K₁ + tK₂ and tC₃ ⊎ C₄Bonnet, Édouard / Duron, Julien / Geniet, Colin / Thomassé, Stéphan / Wesolek, Alexandra et al. | 2023
- 24
-
Faster 0-1-Knapsack via Near-Convex Min-Plus-ConvolutionBringmann, Karl / Cassis, Alejandro et al. | 2023
- 25
-
Funnelselect: Cache-Oblivious Multiple SelectionBrodal, Gerth Stølting / Wild, Sebastian et al. | 2023
- 26
-
Oriented SpannersBuchin, Kevin / Gudmundsson, Joachim / Kalb, Antonia / Popov, Aleksandr / Rehs, Carolin / van Renssen, André / Wong, Sampson et al. | 2023
- 27
-
Online Coalition Formation Under Random Arrival or Coalition DissolutionBullinger, Martin / Romen, René et al. | 2023
- 28
-
On k-Means for Segments and PolylinesCabello, Sergio / Giannopoulos, Panos et al. | 2023
- 29
-
Effective Resistances in Non-Expander GraphsCai, Dongrun / Chen, Xue / Peng, Pan et al. | 2023
- 30
-
New Menger-Like Dualities in Digraphs and Applications to Half-Integral LinkagesCampos, Victor / Costa, Jonas / Lopes, Raul / Sau, Ignasi et al. | 2023
- 31
-
Enumerating Maximal Induced SubgraphsCao, Yixin et al. | 2023
- 32
-
Approximation Algorithm for Norm Multiway CutCarlson, Charlie / Jafarov, Jafar / Makarychev, Konstantin / Makarychev, Yury / Shan, Liren et al. | 2023
- 33
-
Polynomial-Time Approximation of Independent Set Parameterized by TreewidthChalermsook, Parinya / Fomin, Fedor / Hamm, Thekla / Korhonen, Tuukka / Nederlof, Jesper / Orgo, Ly et al. | 2023
- 34
-
Faster Local Motif Clustering via Maximum FlowsChhabra, Adil / Fonseca Faraj, Marcelo / Schulz, Christian et al. | 2023
- 35
-
Primal-Dual Schemes for Online Matching in Bounded Degree GraphsCohen, Ilan Reuven / Peng, Binghui et al. | 2023
- 36
-
Robust and Space-Efficient Dual Adversary Quantum Query AlgorithmsCzekanski, Michael / Kimmel, Shelby / Witter, R. Teal et al. | 2023
- 37
-
Revisiting the Random Subset Sum ProblemDa Cunha, Arthur Carvalho Walraven / d'Amore, Francesco / Giroire, Frédéric / Lesfari, Hicham / Natale, Emanuele / Viennot, Laurent et al. | 2023
- 38
-
Scheduling with a Limited Testing Budget: Tight Results for the Offline and Oblivious SettingsDamerius, Christoph / Kling, Peter / Li, Minming / Xu, Chenyang / Zhang, Ruilong et al. | 2023
- 39
-
A (3/2 + ε)-Approximation for Multiple TSP with a Variable Number of DepotsDeppert, Max / Kaul, Matthias / Mnich, Matthias et al. | 2023
- 40
-
Efficient Parallel Output-Sensitive Edit DistanceDing, Xiangyun / Dong, Xiaojun / Gu, Yan / Liu, Youzhe / Sun, Yihan et al. | 2023
- 41
-
Efficient 1-Laplacian Solvers for Well-Shaped Simplicial Complexes: Beyond Betti Numbers and Collapsing SequencesDing, Ming / Zhang, Peng et al. | 2023
- 42
-
Optimal Energetic Paths for Electric CarsDorfman, Dani / Kaplan, Haim / Tarjan, Robert E. / Zwick, Uri et al. | 2023
- 43
-
Evaluating Restricted First-Order Counting Properties on Nowhere Dense Classes and BeyondDreier, Jan / Mock, Daniel / Rossmanith, Peter et al. | 2023
- 44
-
Online Algorithms with Randomly Infused AdviceEmek, Yuval / Gil, Yuval / Pacut, Maciej / Schmid, Stefan et al. | 2023
- 45
-
The Lawn Mowing Problem: From Algebra to AlgorithmsFekete, Sándor P. / Krupke, Dominik / Perk, Michael / Rieck, Christian / Scheffer, Christian et al. | 2023
- 46
-
Learned Monotone Minimal Perfect HashingFerragina, Paolo / Lehmann, Hans-Peter / Sanders, Peter / Vinciguerra, Giorgio et al. | 2023
- 47
-
Correlating Theory and Practice in Finding Clubs and PlexesFigiel, Aleksander / Koana, Tomohiro / Nichterlein, André / Wünsche, Niklas et al. | 2023
- 48
-
Kernelization for Spreading PointsFomin, Fedor V. / Golovach, Petr A. / Inamdar, Tanmay / Saurabh, Saket / Zehavi, Meirav et al. | 2023
- 49
-
Lossy Kernelization for (Implicit) Hitting Set ProblemsFomin, Fedor V. / Le, Tien-Nam / Lokshtanov, Daniel / Saurabh, Saket / Thomassé, Stéphan / Zehavi, Meirav et al. | 2023
- 50
-
Bootstrapping Dynamic Distance OraclesForster, Sebastian / Goranci, Gramoz / Nazari, Yasamin / Skarlatos, Antonis et al. | 2023
- 51
-
A Sweep-Plane Algorithm for Calculating the Isolation of MountainsFunke, Daniel / Hüning, Nicolai / Sanders, Peter et al. | 2023
- 52
-
A Tight Competitive Ratio for Online Submodular Welfare MaximizationGanz, Amit / Nuti, Pranav / Schwartz, Roy et al. | 2023
- 53
-
First Order Logic and Twin-Width in TournamentsGeniet, Colin / Thomassé, Stéphan et al. | 2023
- 54
-
Improved Approximation Algorithms for the Expanding Search ProblemGriesbach, Svenja M. / Hommelsheim, Felix / Klimm, Max / Schewior, Kevin et al. | 2023
- 55
-
Noisy k-Means++ RevisitedGrunau, Christoph / Özüdoğru, Ahmet Alper / Rozhoň, Václav et al. | 2023
- 56
-
Convergence to Lexicographically Optimal Base in a (Contra)Polymatroid and Applications to Densest Subgraph and Tree PackingHarb, Elfarouk / Quanrud, Kent / Chekuri, Chandra et al. | 2023
- 57
-
Algorithms for Matrix Multiplication via Sampling and Opportunistic Matrix MultiplicationHarris, David G. et al. | 2023
- 58
-
Counting and Sampling Labeled Chordal Graphs in Polynomial TimeHébert-Johnson, Úrsula / Lokshtanov, Daniel / Vigoda, Eric et al. | 2023
- 59
-
Tight Algorithms for Connectivity Problems Parameterized by Clique-WidthHegerfeld, Falko / Kratsch, Stefan et al. | 2023
- 60
-
Pareto Sums of Pareto SetsHespe, Demian / Sanders, Peter / Storandt, Sabine / Truschel, Carina et al. | 2023
- 61
-
Solving Edge Clique Cover Exactly via Synergistic Data ReductionHevia, Anthony / Kallus, Benjamin / McClintic, Summer / Reisner, Samantha / Strash, Darren / Wilson, Johnathan et al. | 2023
- 62
-
Threshold Testing and Semi-Online Prophet InequalitiesHoefer, Martin / Schewior, Kevin et al. | 2023
- 63
-
Parameterized Complexity of Fair Bisection: (FPT-Approximation meets Unbreakability)Inamdar, Tanmay / Lokshtanov, Daniel / Saurabh, Saket / Surianarayanan, Vaishali et al. | 2023
- 64
-
Improved Quantum BoostingIzdebski, Adam / de Wolf, Ronald et al. | 2023
- 65
-
Finding Long Directed Cycles Is Hard Even When DFVS Is Small or Girth Is LargeJacob, Ashwin / Włodarczyk, Michał / Zehavi, Meirav et al. | 2023
- 66
-
5-Approximation for ℋ-Treewidth Essentially as Fast as ℋ-Deletion Parameterized by Solution SizeJansen, Bart M. P. / de Kroon, Jari J. H. / Włodarczyk, Michał et al. | 2023
- 67
-
The Unweighted and Weighted Reverse Shortest Path Problem for Disk GraphsKaplan, Haim / Katz, Matthew J. / Saban, Rachel / Sharir, Micha et al. | 2023
- 68
-
On Fully Dynamic Strongly Connected ComponentsKarczmarz, Adam / Smulewicz, Marcin et al. | 2023
- 69
-
An Improved Approximation Algorithm for the Max-3-Section ProblemKatzelnick, Dor / Pillai, Aditya / Schwartz, Roy / Singh, Mohit et al. | 2023
- 70
-
Fitting Tree Metrics with Minimum DisagreementsKipouridis, Evangelos et al. | 2023
- 71
-
Coloring Tournaments with Few Colors: Algorithms and ComplexityKlingelhoefer, Felix / Newman, Alantha et al. | 2023
- 72
-
Bellman-Ford Is Optimal for Shortest Hop-Bounded PathsKociumaka, Tomasz / Polak, Adam et al. | 2023
- 73
-
Towards Bypassing Lower Bounds for Graph ShortcutsKogan, Shimon / Parter, Merav et al. | 2023
- 74
-
Faster Block Tree ConstructionKöppl, Dominik / Kurpicz, Florian / Meyer, Daniel et al. | 2023
- 75
-
Connectivity Queries Under Vertex Failures: Not Optimal, but PracticalKosinas, Evangelos et al. | 2023
- 76
-
Improved Approximations for Translational Packing of Convex PolygonsKurpisz, Adam / Suter, Silvan et al. | 2023
- 77
-
Structural Parameterizations for Two Bounded Degree Problems RevisitedLampis, Michael / Vasilakis, Manolis et al. | 2023
- 78
-
Massively Parallel Algorithms for the Stochastic Block ModelLi, Zelin / Peng, Pan / Zhu, Xianbin et al. | 2023
- 79
-
Connectivity in the Presence of an OpponentLiang, Zihui / Khoussainov, Bakh / Takisaka, Toru / Xiao, Mingyu et al. | 2023
- 80
-
On the Perturbation Function of Ranking and Balance for Weighted Online Bipartite MatchingLiang, Jingxun / Tang, Zhihao Gavin / Xu, Yixuan Even / Zhang, Yuhao / Zhou, Renfei et al. | 2023
- 81
-
Tight Bounds for Quantum Phase Estimation and Related ProblemsMande, Nikhil S. / de Wolf, Ronald et al. | 2023
- 82
-
A Fine-Grained Classification of the Complexity of Evaluating the Tutte Polynomial on Integer Points Parameterized by Treewidth and CutwidthMannens, Isja / Nederlof, Jesper et al. | 2023
- 83
-
Matching Statistics Speed up BWT ConstructionMasillo, Francesco et al. | 2023
- 84
-
Approximation Schemes for Min-Sum k-ClusteringNaderi, Ismail / Rezapour, Mohsen / Salavatipour, Mohammad R. et al. | 2023
- 85
-
Algorithms for Computing Maximum Cliques in Hyperbolic Random GraphsOh, Eunjin / Oh, Seunghyeok et al. | 2023
- 86
-
Parameterized Complexity of Equality MinCSPOsipov, George / Wahlström, Magnus et al. | 2023
- 87
-
Engineering Fast Algorithms for the Bottleneck Matching ProblemPanagiotas, Ioannis / Pichon, Grégoire / Singh, Somesh / Uçar, Bora et al. | 2023
- 88
-
Subcubic Algorithm for (Unweighted) Unrooted Tree Edit DistancePióro, Krzysztof et al. | 2023
- 89
-
Linear Time Construction of Cover Suffix Tree and ApplicationsRadoszewski, Jakub et al. | 2023
- 90
-
Simultaneous Representation of Interval Graphs in the Sunflower CaseRutter, Ignaz / Stumpf, Peter et al. | 2023
- 91
-
Relaxed Models for Adversarial Streaming: The Bounded Interruptions Model and the Advice ModelSadigurschi, Menachem / Shechner, Moshe / Stemmer, Uri et al. | 2023
- 92
-
Maximal k-Edge-Connected Subgraphs in Almost-Linear Time for Small kSaranurak, Thatchaphol / Yuan, Wuwei et al. | 2023
- 93
-
Approximating Connected Maximum Cuts via Local SearchSchieber, Baruch / Vahidi, Soroush et al. | 2023
- 94
-
Parameterized Matroid-Constrained Maximum CoverageSellier, François et al. | 2023
- 95
-
Fault Tolerance in Euclidean Committee SelectionSonar, Chinmay / Suri, Subhash / Xue, Jie et al. | 2023
- 96
-
Aggregating over Dominated Points by Sorting, Scanning, Zip and Flat MapsSroka, Jacek / Tyszkiewicz, Jerzy et al. | 2023
- 97
-
Improved Algorithms for Online Rent Minimization Problem Under Unit-Size JobsSun, Enze / Yang, Zonghan / Zhang, Yuhao et al. | 2023
- 98
-
Simple Deterministic Approximation for Submodular Multiple Knapsack ProblemSun, Xiaoming / Zhang, Jialin / Zhang, Zhijie et al. | 2023
- 99
-
The Tight Spanning Ratio of the Rectangle Delaunay Triangulationvan Renssen, André / Sha, Yuan / Sun, Yucheng / Wong, Sampson et al. | 2023
- 100
-
Canonization of a Random Graph by Two Matrix-Vector MultiplicationsVerbitsky, Oleg / Zhukovskii, Maksim et al. | 2023
- 101
-
Improved Algorithms for Distance Selection and Related ProblemsWang, Haitao / Zhao, Yiming et al. | 2023
- 102
-
Maximum Coverage in Random-Arrival StreamsWarneke, Rowan / Choudhury, Farhana / Wirth, Anthony et al. | 2023
- 103
-
Efficient Block Approximate Matrix MultiplicationYang, Chuhan / Musco, Christopher et al. | 2023
- 104
-
A Simple Boosting Framework for TransshipmentZuzic, Goran et al. | 2023