Data Structures and Algorithms

Authors and titles for March 2023

[1] arXiv:2303.00259 [pdf, html, other]

Title: Computing All Restricted Skyline Probabilities on Uncertain Datasets

Xiangyu Gao, Jianzhong Li, Dongjing Miao

Comments: Full version, a shorter version to appear in ICDE 2024

Subjects: Data Structures and Algorithms (cs.DS)

[2] arXiv:2303.00480 [pdf, other]

Title: Sampling with Barriers: Faster Mixing via Lewis Weights

Khashayar Gatmiry, Jonathan Kelner, Santosh S. Vempala

Subjects: Data Structures and Algorithms (cs.DS); Logic in Computer Science (cs.LO); Functional Analysis (math.FA); Numerical Analysis (math.NA); Machine Learning (stat.ML)

[3] arXiv:2303.00569 [pdf, other]

Title: A linear time algorithm for linearizing quadratic and higher-order shortest path problems

Eranda Çela, Bettina Klinz, Stefan Lendl, Gerhard J. Woeginger, Lasse Wulf

Subjects: Data Structures and Algorithms (cs.DS)

[4] arXiv:2303.00837 [pdf, other]

Title: Predictive Flows for Faster Ford-Fulkerson

Sami Davies, Benjamin Moseley, Sergei Vassilvitskii, Yuyan Wang

Subjects: Data Structures and Algorithms (cs.DS)

[5] arXiv:2303.01078 [pdf, other]

Title: Pandora's Problem with Combinatorial Cost

Ben Berger, Tomer Ezra, Michal Feldman, Federico Fusco

Journal-ref: EC '23: Proceedings of the 24th ACM Conference on Economics and Computation, 2023

Subjects: Data Structures and Algorithms (cs.DS); Computer Science and Game Theory (cs.GT)

[6] arXiv:2303.01290 [pdf, other]

Title: Solving Distance-constrained Labeling Problems for Small Diameter Graphs via TSP

Tesshu Hanaka, Hirotaka Ono, Kosuke Sugiyama

Comments: 6 pages, 2 figures

Subjects: Data Structures and Algorithms (cs.DS)

[7] arXiv:2303.01414 [pdf, other]

Title: Improved Algorithms for Monotone Moldable Job Scheduling using Compression and Convolution

Kilian Grage, Klaus Jansen, Felix Ohnesorge

Subjects: Data Structures and Algorithms (cs.DS)

[8] arXiv:2303.01453 [pdf, other]

Title: Improved Space Bounds for Learning with Experts

Anders Aamand, Justin Y. Chen, Huy Lê Nguyen, Sandeep Silwal

Subjects: Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG)

[9] arXiv:2303.01478 [pdf, other]

Title: Faster exact and approximation algorithms for packing and covering matroids via push-relabel

Kent Quanrud

Comments: Manuscript submitted to a conference in July 2022. Small edits made in a rebuttal phase in September 2022

Subjects: Data Structures and Algorithms (cs.DS)

[10] arXiv:2303.01673 [pdf, other]

Title: Near Optimal Memory-Regret Tradeoff for Online Learning

Binghui Peng, Aviad Rubinstein

Subjects: Data Structures and Algorithms (cs.DS); Artificial Intelligence (cs.AI); Machine Learning (cs.LG)

[11] arXiv:2303.01709 [pdf, other]

Title: Streaming Algorithms for Learning with Experts: Deterministic Versus Robust

David P. Woodruff, Fred Zhang, Samson Zhou

Subjects: Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG)

[12] arXiv:2303.01726 [pdf, html, other]

Title: Tight bounds for the sensitivity of CDAWGs with left-end edits

Hiroto Fujimaru, Yuto Nakashima, Shunsuke Inenaga

Comments: This is a full version of the paper that appeared in the proceedings of WORDS 2023

Subjects: Data Structures and Algorithms (cs.DS)

[13] arXiv:2303.01957 [pdf, other]

Title: Linear Space Data Structures for Finite Groups with Constant Query-time

Bireswar Das, Anant Kumar, Shivdutt Sharma, Dhara Thakkar

Comments: A preliminary version of this article appeared in the pro- ceedings of the 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM); Combinatorics (math.CO); Group Theory (math.GR)

[14] arXiv:2303.02283 [pdf, other]

Title: On Maximum Bipartite Matching with Separation

Pasin Manurangsi, Erel Segal-Halevi, Warut Suksompong

Journal-ref: Information Processing Letters, 182:106388 (2023)

Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)

[15] arXiv:2303.02390 [pdf, other]

Title: Efficient maximal cliques enumeration in weakly closed graphs

George Manoussakis

Subjects: Data Structures and Algorithms (cs.DS)

[16] arXiv:2303.02474 [pdf, other]

Title: Optimizing Low Dimensional Functions over the Integers

Daniel Dadush, Arthur Léonard, Lars Rohwedder, José Verschae

Comments: To appear at IPCO 2023

Subjects: Data Structures and Algorithms (cs.DS)

[17] arXiv:2303.02491 [pdf, html, other]

Title: Electrical Flows for Polylogarithmic Competitive Oblivious Routing

Gramoz Goranci, Monika Henzinger, Harald Räcke, Sushant Sachdeva, A. R. Sricharan

Comments: ITCS 2024

Subjects: Data Structures and Algorithms (cs.DS)

[18] arXiv:2303.02687 [pdf, other]

Title: Expansion Lemma -- Variations and Applications to Polynomial-Time Preprocessing

Ashwin Jacob, Diptapriyo Majumdar, Venkatesh Raman

Comments: Accepted to Algorithms - Special Issue "Surveys in Algorithm Analysis and Complexity Theory"

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

[19] arXiv:2303.03125 [pdf, html, other]

Title: A Simple 2-Approximation for Maximum-Leaf Spanning Tree

I-Cheng Liao, Hsueh-I Lu

Comments: 10 pages, 4 figures, fixing typos of Equation (3)

Journal-ref: International Journal of Foundations of Computer Science, 2023

Subjects: Data Structures and Algorithms (cs.DS)

[20] arXiv:2303.03705 [pdf, other]

Title: Fairness-aware Maximal Biclique Enumeration on Bipartite Graphs

Ziqi Yin, Qi Zhang, Wentao Zhang, Rong-Hua Li, Guoren Wang

Comments: Accepte by ICDE 2023

Subjects: Data Structures and Algorithms (cs.DS); Databases (cs.DB)

[21] arXiv:2303.04199 [pdf, other]

Title: Diversity Embeddings and the Hypergraph Sparsest Cut

Adam D. Jozefiak, F. Bruce Shepherd

Subjects: Data Structures and Algorithms (cs.DS)

[22] arXiv:2303.04205 [pdf, other]

Title: Investigating the complexity of the double distance problems

Marilia D. V. Braga, Leonie R. Brockmann, Katharina Klerx, Jens Stoye

Comments: 24 pages, 26 figures

Subjects: Data Structures and Algorithms (cs.DS)

[23] arXiv:2303.04478 [pdf, other]

Title: Change a Bit to save Bytes: Compression for Floating Point Time-Series Data

Francesco Taurone, Daniel E. Lucani, Marcell Fehér, Qi Zhang

Journal-ref: 2023 IEEE International Conference on Communications (ICC): SAC Cloud Computing, Networking and Storage Track (IEEE ICC'23 - SAC-02 CCNS Track)

Subjects: Data Structures and Algorithms (cs.DS)

[24] arXiv:2303.04722 [pdf, other]

Title: B-Treaps Revised: Write Efficient Randomized Block Search Trees with High Load

Roodabeh Safavi, Martin P. Seybold

Subjects: Data Structures and Algorithms (cs.DS); Computational Geometry (cs.CG)

[25] arXiv:2303.05012 [pdf, other]

Title: Spatio-Temporal Trajectory Similarity Measures: A Comprehensive Survey and Quantitative Study

Danlei Hu, Lu Chen, Hanxi Fang, Ziquan Fang, Tianyi Li, Yunjun Gao

Comments: 20 pages, 21 figures

Subjects: Data Structures and Algorithms (cs.DS)

[26] arXiv:2303.05067 [pdf, other]

Title: Robust optimization with belief functions

Marc Goerigk, Romain Guillaume, Adam Kasperski, Paweł Zieliński

Subjects: Data Structures and Algorithms (cs.DS); Optimization and Control (math.OC)

[27] arXiv:2303.05250 [pdf, other]

Title: Distributed Half-Integral Matching and Beyond

Sameep Dahal, Jukka Suomela

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

[28] arXiv:2303.05336 [pdf, other]

Title: Elastic Founder Graphs Improved and Enhanced

Nicola Rizzo, Massimo Equi, Tuukka Norri, Veli Mäkinen

Comments: 47 pages, 10 figures. Extension of conference papers IWOCA 2022 (this https URL , preprint arXiv:2201.06492), CPM 2022 (this https URL ), and of some results from PhD dissertation projects of Massimo Equi (this http URL ) and Tuukka Norri (this http URL )

Subjects: Data Structures and Algorithms (cs.DS)

[29] arXiv:2303.05408 [pdf, html, other]

Title: Fast algorithms for Vizing's theorem on bounded degree graphs

Anton Bernshteyn, Abhishek Dhawan

Comments: 43 pages, 15 figures

Subjects: Data Structures and Algorithms (cs.DS); Distributed, Parallel, and Cluster Computing (cs.DC); Discrete Mathematics (cs.DM); Combinatorics (math.CO)

[30] arXiv:2303.05799 [pdf, other]

Title: Optimal-Hash Exact String Matching Algorithms

Thierry Lecroq

Comments: 14 pages

Subjects: Data Structures and Algorithms (cs.DS)

[31] arXiv:2303.05920 [pdf, other]

Title: Faster Matroid Partition Algorithms

Tatsuya Terao

Comments: 26 pages, 1 figure, A preliminary version appears in ICALP 2023

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

[32] arXiv:2303.06090 [pdf, html, other]

Title: Simple and efficient four-cycle counting on sparse graphs

Paul Burkhardt, David G. Harris

Subjects: Data Structures and Algorithms (cs.DS)

[33] arXiv:2303.06102 [pdf, other]

Title: Bootstrapping Dynamic Distance Oracles

Sebastian Forster, Gramoz Goranci, Yasamin Nazari, Antonis Skarlatos

Subjects: Data Structures and Algorithms (cs.DS)

[34] arXiv:2303.06127 [pdf, other]

Title: Any-Order Online Interval Selection

Allan Borodin, Christodoulos Karavasilis

Comments: 19 pages, 11 figures

Subjects: Data Structures and Algorithms (cs.DS)

[35] arXiv:2303.06288 [pdf, other]

Title: Generalizing Greenwald-Khanna Streaming Quantile Summaries for Weighted Inputs

Sepehr Assadi, Nirmit Joshi, Milind Prabhu, Vihan Shah

Comments: 33 pages, 7 figures, International Conference on Database Theory 2023

Subjects: Data Structures and Algorithms (cs.DS)

[36] arXiv:2303.06488 [pdf, other]

Title: Binary Search with Distance-Dependent Costs

Calvin Leng, David Kempe

Comments: 21 pages, 3 figures

Subjects: Data Structures and Algorithms (cs.DS)

[37] arXiv:2303.07229 [pdf, other]

Title: Optimal Square Detection Over General Alphabets

Jonas Ellert, Paweł Gawrychowski, Garance Gourdel

Comments: extended version of a paper published in SODA 2023

Subjects: Data Structures and Algorithms (cs.DS)

[38] arXiv:2303.07266 [pdf, other]

Title: Computational bounds for the 2048 game

Alexey Slizkov

Comments: 12 pages

Subjects: Data Structures and Algorithms (cs.DS)

[39] arXiv:2303.07290 [pdf, html, other]

Title: Finding Diverse Minimum s-t Cuts

Mark de Berg, Andrés López Martínez, Frits Spieksma

Comments: An earlier version of this work appeared at the 34th International Symposium on Algorithms and Computation (ISAAC 2023). Corrected typos in Section 3 and revised arguments in Section 4. Results unchanged. Added new complexity results in Section 5. Readded missing acknowledgments section

Subjects: Data Structures and Algorithms (cs.DS)

[40] arXiv:2303.07444 [pdf, other]

Title: Polynomial-Time Approximation Schemes for Independent Packing Problems on Fractionally Tree-Independence-Number-Fragile Graphs

Esther Galby, Andrea Munaro, Shizhou Yang

Comments: Full version of a paper to appear in a shorter form in the 39th International Symposium on Computational Geometry (SoCG 2023)

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

[41] arXiv:2303.07923 [pdf, html, other]

Title: FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii

Sayan Bandyapadhyay, William Lochet, Saket Saurabh

Comments: Updated version: fix an error in the proof of Lemma 2.5

Subjects: Data Structures and Algorithms (cs.DS); Computational Geometry (cs.CG)

[42] arXiv:2303.07984 [pdf, html, other]

Title: Interlacing Polynomial Method for the Column Subset Selection Problem

Jian-Feng Cai, Zhiqiang Xu, Zili Xu

Subjects: Data Structures and Algorithms (cs.DS); Functional Analysis (math.FA)

[43] arXiv:2303.07985 [pdf, other]

Title: Logarithmic Weisfeiler--Leman and Treewidth

Michael Levet, Puck Rombach, Nicholas Sieger

Comments: There were minor bugs in this version. We corrected those bugs and folded this result into a different paper: arXiv:2306.17777

Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC); Logic in Computer Science (cs.LO); Combinatorics (math.CO)

[44] arXiv:2303.08118 [pdf, other]

Title: Parameterised Approximation of the Fixation Probability of the Dominant Mutation in the Multi-Type Moran Process

Leslie Ann Goldberg, Marc Roth, Tassilo Constantin Schwarz

Comments: 14 pages

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

[45] arXiv:2303.08219 [pdf, other]

Title: A 2-opt Algorithm for Locally Optimal Set Partition Optimization

Kaan Gokcesu, Hakan Gokcesu

Subjects: Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG); Combinatorics (math.CO); Optimization and Control (math.OC)

[46] arXiv:2303.08904 [pdf, other]

Title: Process Equivalence Problems as Energy Games

Benjamin Bisping

Comments: 29 pages. Code: this https URL

Journal-ref: Extended abstract in: CAV 2023, LNCS 13964, pp. 85--106, 2023

Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC); Formal Languages and Automata Theory (cs.FL)

[47] arXiv:2303.08908 [pdf, other]

Title: Online Bipartite Matching in the Probe-Commit Model

Allan Borodin, Calum MacRury

Comments: Combined journal version of conference papers this https URL and this https URL. arXiv admin note: text overlap with arXiv:2102.04325

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

[48] arXiv:2303.09855 [pdf, other]

Title: High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations

Jianyang Gao, Cheng Long

Comments: This paper has been accepted by SIGMOD 2023

Subjects: Data Structures and Algorithms (cs.DS); Databases (cs.DB); Information Retrieval (cs.IR)

[49] arXiv:2303.10034 [pdf, other]

Title: A Comparison of Dijkstra's Algorithm Using Fibonacci Heaps, Binary Heaps, and Self-Balancing Binary Trees

Rhyd Lewis

Comments: 15 pages, 5 figures, 3 algorithms, 2 tables, source code listing

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

[50] arXiv:2303.10394 [pdf, other]

Title: Explorable families of graphs

Andrzej Pelc

Subjects: Data Structures and Algorithms (cs.DS)