Theory & Algorithms · Computer Science & AI
Data Structures & Algorithms
The newest papers in Data Structures & Algorithms that ReadSearch has read, newest first. Each links to its own page, with its authors, date, where it was published and the original.
1,174 papers, from 4 September 2026 to 5 November 2026: 1,174 arXiv preprints.
Get the few papers worth your time in Data Structures & Algorithms every morning.
Follow Data Structures & Algorithms and ReadSearch reads its new papers each day, then brings you the few worth reading, each with its key finding in a sentence.
Newest papers, page 17
Approximation algorithms for identical parallel machine scheduling with assignment costs
We study non-preemptive scheduling on identical parallel machines in which assigning job $j$ to machine $M_i$ incurs the cost $c_{ij}=a_iw_j+b_j$.A Factor-6 Truthful-in-Expectation Mechanism for Cascade Position Auctions
Position auctions require assigning advertisers to positions and determining their display order.Engineering Lightweight Burrows-Wheeler Transform Construction on the GPU via Prefix-Free Parsing
The Burrows-Wheeler transform (BWT) is the core of many compressed full-text indexes and most read aligners.Random Deletion for Circuits in Regular Matroids
We study a simple random deletion algorithm to find short circuits in regular matroids.New Fault-Tolerant $(α,β)$-Spanners
We present new constructions of vertex fault-tolerant (VFT) $(α,β)$-spanners with substantially improved size bounds.Beyond 3SUM-Hardness for Geometric Problems
Since the early days of fine-grained complexity, many geometric problems have been shown to require quadratic time under the 3SUM Hypothesis.The Exact Robustness of Smith's Rule with Predicted Processing Times
Smith's rule orders jobs by their weight-to-processing-time ratios.Exact Algorithms and Complexity of the Smallest Grammar Problem
The Smallest Grammar Problem (SGP) asks for a smallest straight-line grammar generating a given string, with size measured by the total right-hand-side length.Tightening the Online Bin Packing Gap from Both Sides, and the Limits of the Current Methods
The asymptotic competitive ratio of online bin packing has been bracketed since 2018 by the lower bound 1.54278 of Balogh, Bekesi, Dosa, Epstein and Levin and the upper bound 1.57829 of their…Pareto-optimal Scheduling with Predictions
We study preemptive single-machine scheduling with predictions, where a prediction of the order of the jobs (or of their sizes) is available, and the objective is to minimize the total completion…Single-Machine Guarantees on Unrelated Machines and Beyond: Proportional Fairness for Nonclairvoyant Polytope Scheduling
The Polytope Scheduling Problem (PSP) is a general framework for preemptive scheduling in which feasible instantaneous job allocations form a packing polytope.Combinatorial Minimum Cost Flow in Almost-Linear Time on Dense Graphs
We give a combinatorial algorithm that computes an exact minimum-cost flow in $n^{2+o(1)}$ time.A Linear Lower Bound for Convex Body Chasing in Every $\ell_p$ Norm
We establish an $Ω(d)$ lower bound on the competitive ratio of convex body chasing in $\mathbb{R}^d$ with $\ell_p$ movement costs for any $p \in [1, \infty)$.Deterministic Incremental Triconnectivity in $O(\log^2 n)$ Worst-Case Time
We consider the problem of maintaining the triconnectivity in some biconnected graph G in the incremental dynamic setting.Selection under partial information
The selection problem asks to find the $k$-th smallest element in a given set $X$.Structure and Exact Certification of Nonnegative Tensor Decompositions
We study the structure and exact certification of nonnegative tensor decompositions supplied through rational factor matrices.Proximity Theorem and FPT Algorithm for Minimum Group-labeled Matroid Bases
Let $M$ be a matroid, let $\ell:E(M)\to G$ be a labeling of its elements by an abelian group, and let $F\subseteq G$ be finite.Low-Crossing Spanning Paths via Quasi-Uniform Sampling and their Applications
Given a set system (X, S), we consider the problems of constructing perfect matchings and spanning paths (also known as Welzl orders) of X with low crossing numbers with respect to S. Matchings with…Logarithmic Separation between LZ77 and LZ-End and Grammar Compression
We show that there is a logarithmic separation between LZ77 and LZ-End, and between LZ77 and grammar compression.Compressed Boolean Matrix Multiplication using Bicliques
Boolean matrix multiplication is a fundamental operation in many graph-based applications, including web and social network analysis, information retrieval, and graph query evaluation.