arXiv cs.DS Data Structures and Algorithms

Kaisei Deguchi, Ken-ichi Kawarabayashi, Hirotaka Yoneda, Masataka Yoneda: An $O(n^{0.1537})$-Coloring Algorithm for 3-Colorable Graphs https://arxiv.org/abs/2610.35859 https://arxiv.org/pdf/2610.35859 https://arxiv.org/html/2610.35859

Sharma V. Thankachan: Tiny Suffix Arrays https://arxiv.org/abs/2610.35543 https://arxiv.org/pdf/2610.35543 https://arxiv.org/html/2610.35543

Hadley Black, Arya Mazumdar, Barna Saha, Geelon So: Query Complexity of Learning Axis-Aligned Partitions https://arxiv.org/abs/2610.35495 https://arxiv.org/pdf/2610.35495 https://arxiv.org/html/2610.35495

Gonzalo Navarro: Computation-Friendly Compression of Matrices: Speeding up Linear and Boolean Algebra https://arxiv.org/abs/2610.35362 https://arxiv.org/pdf/2610.35362 https://arxiv.org/html/2610.35362

Zhao Song: Improved Quasi-Polynomial-Time Approximation for Maximum Independent Set https://arxiv.org/abs/2610.35228 https://arxiv.org/pdf/2610.35228 https://arxiv.org/html/2610.35228

Kiarash Banihashem, Samira Goudarzi, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, Morteza Monemizadeh: From Linear to Polylogarithmic: Dynamic Submodular Maximization over Matroids https://arxiv.org/abs/2610.35131 https://arxiv.org/pdf/2610.35131 https://arxiv.org/html/2610.35131

Bo Peng, Zhihao Gavin Tang: Order-selection Prophet Inequality (Almost) Goes I.I.D https://arxiv.org/abs/2610.34892 https://arxiv.org/pdf/2610.34892 https://arxiv.org/html/2610.34892

Armando Rodado Amaris: When is greedy exact for weighted minimum 3-cut? https://arxiv.org/abs/2610.34851 https://arxiv.org/pdf/2610.34851 https://arxiv.org/html/2610.34851

Vinayak M. Kumar: Linear Hashing Is Poissonesque https://arxiv.org/abs/2610.34750 https://arxiv.org/pdf/2610.34750 https://arxiv.org/html/2610.34750

Weitian Tong, Yao Xu: Coordinating Boundaries: Improved Approximation Algorithms for Unweighted Non-Preemptive Throughput Maximization https://arxiv.org/abs/2610.34656 https://arxiv.org/pdf/2610.34656 https://arxiv.org/html/2610.34656

Nicola Wengiel: Online Discrepancy of Sparse Random Vectors over Long Horizons https://arxiv.org/abs/2610.34410 https://arxiv.org/pdf/2610.34410 https://arxiv.org/html/2610.34410

Junqiu Hu, Lingxiao Huang, Jian Li, Baoduo Xu: Tight Coreset Bounds for Euclidean $(k,z)$-Clustering https://arxiv.org/abs/2610.34373 https://arxiv.org/pdf/2610.34373 https://arxiv.org/html/2610.34373

Hongyi Chen, Tianyi Zhang: Bicriteria Approximate Navigable Graphs in General Metrics https://arxiv.org/abs/2610.34302 https://arxiv.org/pdf/2610.34302 https://arxiv.org/html/2610.34302

Yang P. Liu, Hoai-An Nguyen, Vihan Shah, David P. Woodruff: A Nearly Optimal Min-Cut Algorithm for Dynamic Streams https://arxiv.org/abs/2610.34097 https://arxiv.org/pdf/2610.34097 https://arxiv.org/html/2610.34097

Merav Parter, Elizaveta Popova, Elad Tzalik: New Fault-Tolerant $(\alpha,\beta)$-Spanners https://arxiv.org/abs/2610.33934 https://arxiv.org/pdf/2610.33934 https://arxiv.org/html/2610.33934

Karthekeyan Chandrasekaran, Chandra Chekuri, Weihao Zhu: Random Deletion for Circuits in Regular Matroids https://arxiv.org/abs/2610.33918 https://arxiv.org/pdf/2610.33918 https://arxiv.org/html/2610.33918

Florian Kurpicz, Maximilian Paris: Engineering Lightweight Burrows-Wheeler Transform Construction on the GPU via Prefix-Free Parsing https://arxiv.org/abs/2610.33889 https://arxiv.org/pdf/2610.33889 https://arxiv.org/html/2610.33889

Wei Li: Approximation algorithms for identical parallel machine scheduling with assignment costs https://arxiv.org/abs/2610.33666 https://arxiv.org/pdf/2610.33666 https://arxiv.org/html/2610.33666

Andrew Krapivin, William Kuszmaul: Optimal Worst-Case Open Addressing: Braided Cuckoo Hashing https://arxiv.org/abs/2610.33229 https://arxiv.org/pdf/2610.33229 https://arxiv.org/html/2610.33229

[2026-10-27 Tue (UTC), 19 new articles found for csDS Data Structures and Algorithms]

J{\o}rgen Bang-Jensen, St\'ephane Bessy, Amadeus Reinald: Acyclic 2-edge-coloured graphs: polynomial-time linkages and colouring hardness https://arxiv.org/abs/2610.32954 https://arxiv.org/pdf/2610.32954 https://arxiv.org/html/2610.32954

Ilias Diakonikolas, Jelena Diakonikolas, Puqian Wang, Nikos Zarifis: Learning Positive Linear Combinations of ReLUs in Fully Polynomial Time https://arxiv.org/abs/2610.32940 https://arxiv.org/pdf/2610.32940 https://arxiv.org/html/2610.32940

Nicol\'as Araya, Jos\'e Zagal, Cecilia Hern\'andez, Gonzalo Navarro: Compressed Boolean Matrix Multiplication using Bicliques https://arxiv.org/abs/2610.32836 https://arxiv.org/pdf/2610.32836 https://arxiv.org/html/2610.32836

Haoming Wang, Ming Yuan: Structure and Exact Certification of Nonnegative Tensor Decompositions https://arxiv.org/abs/2610.32787 https://arxiv.org/pdf/2610.32787 https://arxiv.org/html/2610.32787

Benjamin Aram Berendsohn: Selection under partial information https://arxiv.org/abs/2610.32731 https://arxiv.org/pdf/2610.32731 https://arxiv.org/html/2610.32731

Niels Inselmann Christiansen, Eva Rotenberg: Deterministic Incremental Triconnectivity in $O(\log^2 n)$ Worst-Case Time https://arxiv.org/abs/2610.32721 https://arxiv.org/pdf/2610.32721 https://arxiv.org/html/2610.32721

Nicolas Christianson: A Linear Lower Bound for Convex Body Chasing in Every $\ell_p$ Norm https://arxiv.org/abs/2610.32670 https://arxiv.org/pdf/2610.32670 https://arxiv.org/html/2610.32670

Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak: Combinatorial Minimum Cost Flow in Almost-Linear Time on Dense Graphs https://arxiv.org/abs/2610.32556 https://arxiv.org/pdf/2610.32556 https://arxiv.org/html/2610.32556

Alexander Lindermayr, Sven J\"ager, Bart Zondervan: Single-Machine Guarantees on Unrelated Machines and Beyond: Proportional Fairness for Nonclairvoyant Polytope Scheduling https://arxiv.org/abs/2610.32545 https://arxiv.org/pdf/2610.32545 https://arxiv.org/html/2610.32545

Ziyad Benomar, Vianney Perchet: Pareto-optimal Scheduling with Predictions https://arxiv.org/abs/2610.32503 https://arxiv.org/pdf/2610.32503 https://arxiv.org/html/2610.32503

Karyamsetty Martin: Tightening the Online Bin Packing Gap from Both Sides, and the Limits of the Current Methods https://arxiv.org/abs/2610.32367 https://arxiv.org/pdf/2610.32367 https://arxiv.org/html/2610.32367

Xiangle Chen: Exact Algorithms and Complexity of the Smallest Grammar Problem https://arxiv.org/abs/2610.32298 https://arxiv.org/pdf/2610.32298 https://arxiv.org/html/2610.32298

Ohad Ayalon, Ilan Reuven Cohen: The Exact Robustness of Smith's Rule with Predicted Processing Times https://arxiv.org/abs/2610.32197 https://arxiv.org/pdf/2610.32197 https://arxiv.org/html/2610.32197

Nick Fischer: Beyond 3SUM-Hardness for Geometric Problems https://arxiv.org/abs/2610.32162 https://arxiv.org/pdf/2610.32162 https://arxiv.org/html/2610.32162

[2026-10-26 Mon (UTC), 14 new articles found for csDS Data Structures and Algorithms]

Sophia Heimann, Hung P. Hoang, Stefan Hougardy: Closing All-Exp Gaps in Local Search for the Traveling Salesman Problem and Maximum Constraint Assignment https://arxiv.org/abs/2610.31513 https://arxiv.org/pdf/2610.31513 https://arxiv.org/html/2610.31513

Amir Carmel, Robert Krauthgamer: Coresets for $k$-Means: When Does Uniform Sampling Suffice? https://arxiv.org/abs/2610.31491 https://arxiv.org/pdf/2610.31491 https://arxiv.org/html/2610.31491

Jackson Bibbens, Adam Lechowicz, Nicolas Christianson, Bo Sun, Mohammad Hajiesmaili: Peak-Aware One-Way Trading: Competitive and Learning-Augmented Algorithms for Energy Procurement https://arxiv.org/abs/2610.31447 https://arxiv.org/pdf/2610.31447 https://arxiv.org/html/2610.31447

Yuhao Guo, Seth Pettie, Chengzhang Wan: A Sharp Analysis of Fixed Offset Hash Tables https://arxiv.org/abs/2610.31363 https://arxiv.org/pdf/2610.31363 https://arxiv.org/html/2610.31363

Philip Bille, Inge Li G{\o}rtz, Christoffer Krogh, Christian M{\o}ller Mikkelstrup: Hardness and Approximation for Compressing Deterministic Finite Automata https://arxiv.org/abs/2610.31273 https://arxiv.org/pdf/2610.31273 https://arxiv.org/html/2610.31273

Duc A. Hoang: Kempe Reachability with $k\geq 3$ Colors Is $\mathsf{PSPACE}$-Complete on Claw-Free Graphs https://arxiv.org/abs/2610.31263 https://arxiv.org/pdf/2610.31263 https://arxiv.org/html/2610.31263

Duc A. Hoang: A Polynomial-Time Algorithm for $k$-Path Vertex Cover Reconfiguration on Trees under Token Sliding https://arxiv.org/abs/2610.31261 https://arxiv.org/pdf/2610.31261 https://arxiv.org/html/2610.31261

Jaros{\l}aw Byrka, Yuhao Guo, Yang Hu, Shi Li, Yongho Shin, Phanu Vajanopath, Chengzhang Wan, Zaixuan Wang: Iterative Randomized Rounding for Better-Than-2 k-Median Approximation https://arxiv.org/abs/2610.31229 https://arxiv.org/pdf/2610.31229 https://arxiv.org/html/2610.31229

Deepak Bhati, Pranjal Dutta, Antoine Joux, Mahesh Sreekumar Rajasree, Karol Wegrzycki: Pigeonhole Equal Subset Sum: Subexponential Algorithm, Tight Lower Bounds, and Average-Case Analysis https://arxiv.org/abs/2610.31056 https://arxiv.org/pdf/2610.31056 https://arxiv.org/html/2610.31056

Chandra Kanta Mohapatra: Near-Quadratic Time Multivariate Polynomial Interpolation https://arxiv.org/abs/2610.30907 https://arxiv.org/pdf/2610.30907 https://arxiv.org/html/2610.30907

Haoran wang: Optimal Mixing for Local Edge-Coloring Dynamics on Trees https://arxiv.org/abs/2610.30625 https://arxiv.org/pdf/2610.30625 https://arxiv.org/html/2610.30625

Hiroyasu Usami: The Cost of Missed States: Online Tracking with Current-Observation Resets https://arxiv.org/abs/2610.30505 https://arxiv.org/pdf/2610.30505 https://arxiv.org/html/2610.30505

Joseph Seffi Naor, Tomer Tsachor: Tight Bounds for Paging with Time Windows and Joint Replenishment with Varying Opening Costs https://arxiv.org/abs/2610.30430 https://arxiv.org/pdf/2610.30430 https://arxiv.org/html/2610.30430

[2026-10-23 Fri (UTC), 13 new articles found for csDS Data Structures and Algorithms]

Frank Kammer, Sandra Kiefer, Johannes Meintrup: Temporal Exploration and Rendezvous via Weisfeiler-Leman Colorings https://arxiv.org/abs/2610.30123 https://arxiv.org/pdf/2610.30123 https://arxiv.org/html/2610.30123