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 13
$k$-Center under Weak and Strong Distance Oracles with an Application to Minimum Sum of Radii Clustering
In the weak-strong distance oracle model of Bateni, Dharangutte, Jayaram and Wang (COLT 2024), a metric $(X,d)$ on $n$ points is accessed through two oracles: a cheap weak oracle that returns each…Building On Learning-Augmented Online Sorting
Online sorting is a problem that has gained attention recently, and is a natural translation of sorting into an online setting.Tight Asymptotic Bounds on the Size of Order Graphs
Order graphs were introduced by Arroyuelo et al.\ (TODS 2024) as a generalization of the ring index, to support worst-case optimal joins on relations of arity $d$ while storing as few columns as…Substring Complexity in BWT-Runs Bounded Space
Given a string $T[1..n]$, its substring complexity is defined as $δ=\max_k d_k/k$, where $d_k$ is the number of its distinct substrings of length $k$ in $T$.Constant-Factor Approximation for Non-Splitting Coflow Scheduling in Heterogeneous Parallel Networks via Iterative Relaxation
Coflows capture the collective communication requirements of data-parallel applications, and scheduling them well is essential to the performance of modern data centers.Parameterized Approximation of Max k-Weight CSP: A Dichotomy for Boolean Languages
We study \textsc{Max $k$-Weight CSP}: maximize the satisfied weight of Boolean constraints with nonnegative rational weights by setting at most $k$ variables to $1$.Four-Coloring Planar Graphs in Linear Time
The famous Four Color Theorem (4CT) states that any planar graph can be colored with four colors, but how do we find a 4-coloring?A Single-Exponential Time Algorithm for the Maximum-Cardinality Weakly Stable Matching Problem with Ties and Incomplete Lists
We study Stable Marriage with Ties and Incomplete lists (SMTI) under weak stability.From Trees to Binary Trees: Approximation Algorithms and a PTAS
Kellerhals, Krebs, Nichterlein, and Schmid introduced the optimization problem Tree in Binary Tree (TBT), where, given a tree $T$, the task is to find a binary tree $S^*$ with $V(T)=V(S^*)$ that…Communication-Oblivious Permutation and Sorting
With the help of secure hardware such as trusted execution environments (TEEs), private data can be uploaded and computed in untrusted cloud clusters, so that an adversary controlling the cloud can…An Exact Parallel Dense Gauss-Seidel Algorithm with Trade-Offs between Parallel Execution Time and Preprocessing Time
The Gauss-Seidel iterative method is commonly used for solving systems of linear equations because of its good convergence properties.Accumulating Pruning Constraints: New Exact Polynomial-Space Algorithms for Max 2-SAT
We present deterministic polynomial-space algorithms that solve Max 2-SAT on $n$ variables exactly in time $\Ostar(2^{(1-γ)n})$, for a fixed $γ>0$, on several classes of instances whose clause…Counting approximate breakpoint medians of random genomes
Unsigned linear unichromosomal genomes with genes labeled 1, . . . , n are represented by permutations of these labels, whose adjacencies are the unordered pairs of genes occurring consecutively.Nearly Optimal Sparse Navigable Graphs in General Metrics
We study approximation algorithms for constructing sparse navigable graphs in general metrics.Retrieval Sequencing in a Compact Storage System with Side Access
In a compact storage system with side access, bins are arranged in adjacent vertical stacks.Layering and reverse extension for weighted $k$-path vertex cover
We study the weighted $k$-path vertex cover problem for any fixed integer $k \ge 2$, in which a vertex non-negatively weighted simple graph $G = (V, E)$ is given and one wants to find a…Leveraging Recourse and Size Bounds for OnlineKnapsack with Removable Items
In the online unweighted knapsack problem, items arrive sequentially and must be accepted or rejected immediately for a bounded-capacity knapsack, aiming to maximize the total size of accepted items.Half-Optimal Induced Matchings in Random Graphs: Online and Low-Degree Algorithms
For many optimization problems on random graphs, most prominently the largest independent set problem, natural algorithms reach only half the optimum, and such factor-two gaps are known to be sharp…Zero-freeness for Random Regular Graphs up to the Replica Symmetry Breaking Threshold
We study antiferromagnetic spin systems on random regular graphs through the lens of the phase transitions characterized by the complex zeros of the partition function.Exact Competitive Ratios of Index Rules for Scheduling with Obligatory Testing
We revisit scheduling with obligatory testing, where each job consists of two operations: a test with an initially known time and an operation whose processing time is revealed upon completion of…