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 20
An Exact Polynomial-Time Algorithm for the Minimum Shared-Power Edge Cut Problem
The Minimum Shared-Power Edge Cut (MSPEC) problem seeks to disconnect two designated terminals with minimum total power by assigning powers to graph vertices and deleting every edge for which the…Improved Approximation and Hardness Results for the Monitoring Edge-Geodetic Set Problem
We study the \emph{Monitoring Edge-Geodetic Set} problem (MEG-Set), which asks for a minimum-cardinality set $M$ of vertices of an undirected graph $G$ of $n$ vertices such that every edge of $G$…Splitting Planar Necklaces with Few Straight Cuts
In the classical necklace splitting problem, beads of different colors lie on a line, and the goal is to divide them among $k$ agents using as few cuts as possible so that every agent receives the…Fixed Sets and the Hardness of Computing Correlated Equilibria
We show that computing an approximate correlated equilibrium of a polytope game is PPAD-complete, and thus polynomial-time equivalent to finding a Nash equilibrium.Subjective Valuations Make It Hard to be Fair: The Complexity of Resource Allocation to Groups of Agents
We study the parameterized complexity of finding an EF1 allocation of indivisible items in the group-sharing setting, which has received increasing attention in recent years.ARRIVAL in cube-root subexponential time
In the ARRIVAL problem, a token travels through a switch digraph: at every vertex, it leaves along one of two out-arcs, and the two are used alternately.Improved Approximation for Unsplittable Capacitated Vehicle Routing Using Quota Trees
In the Unsplittable Capacitated Vehicle Routing Problem (UCVRP), we are given a set $V$ of $n$ clients with normalized demands $d_v \in (0,1]$, a depot $r$, a unit vehicle capacity, and symmetric…Diverse Schedules for Makespan Minimization on Unrelated Machines
We study makespan minimization on unrelated machines with the additional goal of constructing diverse schedules: Instead of outputting a single schedule, we seek a collection of schedules with…Dynamic Distances Without Matrix Inverse
We study the fully dynamic exact distance problem in unweighted directed graphs, where the graph undergoes edge insertions and deletions, and the distance between two query vertices must be reported.Birthday Estimators Are Uniformly Optimal for Renyi Entropy
Collisions are a basic probe of unknown distributions, used for testing and for counting substructures in graphs, and they underlie Rényi entropy, a fundamental measure of uncertainty with…Amplified Pruning and Path Selectors for Deterministic Radio Gossiping
We study deterministic gossiping in unknown strongly connected directed radio networks with $n$ vertices, $m$ arcs, and distinct identifiers in $[N]$, where $N=n^{\mathcal O(1)}$.Solving problems in RDV Graphs faster and easier
In interval graphs and many generalizations thereof, problems such as Matching, Independent Set, and Dominating Set can be solved with simple greedy algorithms in linear (i.e., $O(m+n)$) time.The Optimal Sampler for Diverse TSP Solutions: Characterization, Limits, and Learning
We address the Diverse Traveling Salesman Problem (D-TSP) that seeks a set of $k$ distinct TSP tours.Hadamard Transforms for Dimension Reduction
Using the Hadamard matrix for dimension reduction can accelerate the computation due to the fast Hadamard transform.Exact minimum Birkhoff decompositions of doubly stochastic matrices with finite precision
The minimum Birkhoff decomposition problem asks for a representation of a doubly stochastic matrix as a convex combination of as few permutation matrices as possible.Integer Programing: An Algorithm with Exponent Linear in the Dimension
We study integer programs in standard form $\min\{\mathbf{c}^{\mathsf{T}}\mathbf{x}:A\mathbf{x}=\mathbf{b},\ \mathbf{l}\leq\mathbf{x}\leq\mathbf{u},\ \mathbf{x}\in\mathbb{Z}^n\}$, where…Internalizing Chain-of-thought into Looped Transformers
Chain-of-thought (CoT) enables constant-bit-size transformers to perform general-purpose computation through generated tokens (Li and Wang, 2025a), whereas looped transformers carry out the same…Solving Classes of Linear Programs with Strongly Polynomial Straight Line Complexity in Strongly Polynomial Time
Recently, Allamigeon, Dadush, Loho, Natura, and Végh (ADLNV, SICOMP 2025) introduced an interior point method for linear programs whose number of iterations is bounded by the so-called straight line…Dynamic $(Δ+1)$-Coloring Against an Adaptive Adversary: Faster, Simpler, Worst-Case, and Bounded Recourse
We study fully dynamic $(Δ+1)$-coloring against an adaptive adversary.Ski Rental with Uniform Stochastic Signals
Ski rental is one of the most fundamental online problems, where an agent repeatedly decides whether it should continue renting for a service, or buy it at a one-time fixed cost.