Daily edition · Algorithms
TILens turns technical updates into a focused daily brief: official releases, trusted reporting, and practitioner analysis, deduplicated and organized by topic.
arXiv:2608.27607v1 Announce Type: new Abstract: We give an approximation algorithm for the rural postman problem with approximation ratio strictly smaller than $3/2$. We obtain this result by adapting to the rural…
arXiv:2608.28512v1 Announce Type: new Abstract: First proposed in 1968, quadratic probing has stood for more than half a century as one of the simplest and most widely used hash-table designs in computer science. It is…
arXiv:2605.09711v3 Announce Type: replace Abstract: In the \emph{dynamic edge coloring} problem, one has to maintain a graph of maximum degree $\Delta$ with at most $\Delta+c$ colors, under edge updates. A prominent…
arXiv:2608.28031v1 Announce Type: new Abstract: The canonical Bethe approximation gives a deterministic approximation to the permanent of every nonnegative matrix within a factor of $(\sqrt{2})^n$. We improve the base…
arXiv:2608.22159v2 Announce Type: replace-cross Abstract: We prove that for every fixed inverse temperature $\beta < 1 / 2$, with high probability over the disorder, the single-site Glauber dynamics for the $n$-spin…
arXiv:2602.23999v2 Announce Type: replace-cross Abstract: Approximate nearest neighbor search (ANNS) on GPUs is gaining increasing popularity for modern retrieval and recommendation workloads that operate over massive…
arXiv:2608.28566v1 Announce Type: new Abstract: We study the mixing time of weighted Dikin walks for sampling from exponential distributions on polytopes and truncated positive-semidefinite (PSD) cones. Our first result…
arXiv:2604.17945v2 Announce Type: replace Abstract: We study flow shop scheduling with stochastic reentry, where jobs must complete multiple passes through the entire shop, and the number of passes that a job requires…
arXiv:2608.28313v1 Announce Type: new Abstract: Motivated by non-uniform edge failures in network design, we introduce a multi-tier model of flexible graph connectivity. In k-tier Flexible Graph Connectivity (k-tier…
arXiv:2604.04186v2 Announce Type: replace Abstract: Given a weighted digraph $G$, a $(t,g,\mu)$-DAG cover is a collection of $g$ dominating DAGs $D_1,\dots,D_g$ such that all distances are approximately preserved: for…
arXiv:2608.27616v1 Announce Type: new Abstract: Range filters are compact probabilistic data structures that answer approximate range emptiness queries. They are used in many domains, e.g., in key-value stores, to…
arXiv:2608.27600v1 Announce Type: new Abstract: We revisit the $d$-dimensional Vector Knapsack problem ($d$-Knapsack): Given a $d$-dimensional capacity vector and a set of items, each with a $d$-dimensional weight…
arXiv:2608.27896v1 Announce Type: new Abstract: We study differentially private (DP) $k$-means and $k$-median clustering in the online streaming setting. In this model, points arrive sequentially, and at each time step,…
arXiv:2608.28539v1 Announce Type: cross Abstract: In this work, we present the first analysis of low degree polynomial threshold functions for the natural hypothesis testing problem of detecting the noisy random lift of…
arXiv:2608.28462v1 Announce Type: new Abstract: The classical memory-allocation problem captures the task of placing objects of different sizes in memory, while minimizing the so-called memory high-water mark. It has…
arXiv:2608.27986v1 Announce Type: new Abstract: Numerical integration---approximating the integral of a function $f$ using $n$ point evaluations---is a central task in science and engineering. The two main paradigms for…
arXiv:2608.07187v2 Announce Type: replace Abstract: Let $G$ be an undirected unweighted planar graph and let $S=(s_0,\dots,s_{k-1})$ be the vertices of a designated face, listed in cyclic order. Consider a vector that…
arXiv:2608.28094v1 Announce Type: new Abstract: We study random sketching matrices with Khatri-Rao structure. In particular, we consider the Khatri-Rao product (i.e., column-wise tensor product) $A_1\odot\cdots\odot A_d…
arXiv:2608.28081v1 Announce Type: new Abstract: We study the \emph{connected $k$-median} clustering problem, a clustering problem that augments the classical $k$-median objective with connectivity constraints. We focus…
arXiv:2608.28452v1 Announce Type: cross Abstract: A conjecture of Koml\'os states that the combinatorial discrepancy of any matrix $A\in\mathbb R^{m\times n}$ whose columns have Euclidean norm at most one is bounded by…
Showing 1 day · 27 items available
