Data Structures and Algorithms

Authors and titles for cs.DS in Aug 2023

[1]  arXiv:2308.00306 [pdf, other]

Title: Smoothed Analysis of the 2-Opt Heuristic for the TSP under Gaussian Noise

Authors: Marvin Künnemann, Bodo Manthey, Rianne Veenstra

Comments: Combination of an ISAAC 2013 paper by Bodo Manthey and Rianne Veenstra and an ICALP 2015 paper by Marvin K\"unnemann and Bodo Manthey. The results of the ISAAC 2013 paper have been improved

Subjects: Data Structures and Algorithms (cs.DS)

[2]  arXiv:2308.00501 [pdf, ps, other]

Title: Structural Parameterizations of the Biclique-Free Vertex Deletion Problem

Authors: Lito Goldmann, Leon Kellerhals, Tomohiro Koana

Subjects: Data Structures and Algorithms (cs.DS)

[3]  arXiv:2308.00503 [pdf, ps, other]

Title: Massively Parallel Algorithms for High-Dimensional Euclidean Minimum Spanning Tree

Authors: Rajesh Jayaram, Vahab Mirrokni, Shyam Narayanan, Peilin Zhong

Subjects: Data Structures and Algorithms (cs.DS)

[4]  arXiv:2308.00555 [pdf, other]

Title: Shortcut Partitions in Minor-Free Graphs: Steiner Point Removal, Distance Oracles, Tree Covers, and More

Authors: Hsien-Chih Chang, Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, Cuong Than

Subjects: Data Structures and Algorithms (cs.DS)

[5]  arXiv:2308.00793 [pdf, ps, other]

Title: Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in-$f$ Time Barrier

Authors: Anton Bukov, Shay Solomon, Tianyi Zhang

Comments: Abstract shortened to meet arXiv requirements

Subjects: Data Structures and Algorithms (cs.DS)

[6]  arXiv:2308.00925 [pdf, ps, other]

Title: An Algorithm for the Longest Common Subsequence and Substring Problem

Authors: R. Li, J. Deka, K. Deka

Subjects: Data Structures and Algorithms (cs.DS)

[7]  arXiv:2308.01037 [pdf, other]

Title: A Fast Monte Carlo algorithm for evaluating matrix functions with application in complex networks

Authors: Nicolas L. Guidotti, Juan A. Acebrón, José Monteiro

Comments: To be published in the Journal of Scientific Computing

Subjects: Data Structures and Algorithms (cs.DS)

[8]  arXiv:2308.01199 [pdf, other]

Title: One Tree to Rule Them All: Poly-Logarithmic Universal Steiner Tree

Authors: Costas Busch, Da Qi Chen, Arnold Filtser, Daniel Hathcock, D Ellis Hershkowitz, Rajmohan Rajaraman

Comments: @FOCS23

Subjects: Data Structures and Algorithms (cs.DS)

[9]  arXiv:2308.01286 [pdf, ps, other]

Title: Enumeration Kernels of Polynomial Size for Cuts of Bounded Degree

Authors: Diptapriyo Majumdar

Comments: There have been major revision in the technicalities and proofs of the paper

Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM)

[10]  arXiv:2308.01322 [pdf, ps, other]

Title: An Algorithm for the Constrained Longest Common Subsequence and Substring Problem

Authors: R. Li, J. Deka, K. Deka, D. Li

Comments: arXiv admin note: text overlap with arXiv:2308.00925

Subjects: Data Structures and Algorithms (cs.DS)

[11]  arXiv:2308.01359 [pdf, other]

Title: Fast Coloring Despite Congested Relays

Authors: Maxime Flin, Magnús M. Halldórsson, Alexandre Nolin

Comments: 37 pages. To appear in proceedings of DISC 2023

Subjects: Data Structures and Algorithms (cs.DS); Distributed, Parallel, and Cluster Computing (cs.DC)

[12]  arXiv:2308.01406 [pdf, ps, other]

Title: Optimal Online Discrepancy Minimization

Authors: Janardhan Kulkarni, Victor Reis, Thomas Rothvoss

Comments: 22 pages

Subjects: Data Structures and Algorithms (cs.DS)

[13]  arXiv:2308.01534 [pdf, other]

Title: Simultaneously Approximating All $\ell_p$-norms in Correlation Clustering

Authors: Sami Davies, Benjamin Moseley, Heather Newman

Comments: 27 pages, 2 figures

Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM)

[14]  arXiv:2308.01574 [pdf, ps, other]

Title: Another Hamiltonian Cycle in Bipartite Pfaffian Graphs

Authors: Andreas Björklund, Petteri Kaski, Jesper Nederlof

Comments: Adds analysis of Thomason's lollipop method

Subjects: Data Structures and Algorithms (cs.DS)

[15]  arXiv:2308.01598 [pdf, other]

Title: Meta-theorems for Parameterized Streaming Algorithms

Authors: Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi

Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM)

[16]  arXiv:2308.02188 [pdf, other]

Title: Kernelization of Counting Problems

Authors: Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, Meirav Zehavi

Subjects: Data Structures and Algorithms (cs.DS)

[17]  arXiv:2308.02269 [pdf, other]

Title: Optimally Computing Compressed Indexing Arrays Based on the Compact Directed Acyclic Word Graph

Authors: Hiroki Arimura, Shunsuke Inenaga, Yasuaki Kobayashi, Yuto Nakashima, Mizuki Sue

Comments: The short version of this paper will appear in SPIRE 2023, Pisa, Italy, September 26-28, 2023, Lecture Notes in Computer Science, Springer

Subjects: Data Structures and Algorithms (cs.DS); Formal Languages and Automata Theory (cs.FL); Information Retrieval (cs.IR)

[18]  arXiv:2308.02651 [pdf, other]

Title: Single-Source Unsplittable Flows in Planar Graphs

Authors: Vera Traub, Laura Vargas Koch, Rico Zenklusen

Subjects: Data Structures and Algorithms (cs.DS)

[19]  arXiv:2308.02875 [pdf, ps, other]

Title: An Overview of Analysis Methods and Evaluation Results for Caching Strategies

Authors: Gerhard Hasslinger, Mahshid Okhovatzadeh, Konstantinos Ntougias, Frank Hasslinger, Oliver Hohlfeld

Comments: 25 pages

Journal-ref: Computer Networks Volume 228 Year 2023

Subjects: Data Structures and Algorithms (cs.DS)

[20]  arXiv:2308.02901 [pdf, other]

Title: A logarithmic approximation algorithm for the activation edge multicover problem

Authors: Zeev Nutov

Subjects: Data Structures and Algorithms (cs.DS)

[21]  arXiv:2308.02946 [pdf, ps, other]

Title: Solving a Random Asymmetric TSP Exactly in Quasi-Polynomial Time w.h.p

Authors: Tolson Bell, Alan Frieze

Comments: 19 pages

Subjects: Data Structures and Algorithms (cs.DS); Combinatorics (math.CO)

[22]  arXiv:2308.03075 [pdf, ps, other]

Title: Knapsack with Small Items in Near-Quadratic Time

Authors: Karl Bringmann

Comments: 28 pages, accepted at STOC'24

Subjects: Data Structures and Algorithms (cs.DS)

[23]  arXiv:2308.03289 [pdf, ps, other]

Title: Testing Graph Properties with the Container Method

Authors: Eric Blais, Cameron Seth

Subjects: Data Structures and Algorithms (cs.DS)

[24]  arXiv:2308.03516 [pdf, other]

Title: An Improved Approximation Algorithm for the Max-$3$-Section Problem

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

Subjects: Data Structures and Algorithms (cs.DS)

[25]  arXiv:2308.03578 [pdf, other]

Title: TeraHAC: Hierarchical Agglomerative Clustering of Trillion-Edge Graphs

Authors: Laxman Dhulipala, Jason Lee, Jakub Łącki, Vahab Mirrokni

Comments: To appear at SIGMOD 2024

Subjects: Data Structures and Algorithms (cs.DS); Databases (cs.DB); Distributed, Parallel, and Cluster Computing (cs.DC); Information Retrieval (cs.IR)