Daily edition · Algorithms
TILens turns technical updates into a focused daily brief: official releases, trusted reporting, and practitioner analysis, deduplicated and organized by topic.
48 articles · 2 sources · 48 papers ·
Top topics: Algorithms · AI
arXiv:2611.08963v1 Announce Type: new Abstract: We give a global spectral bound for the Sinkhorn--Knopp (SK) algorithm. Let $A$ be a row-stochastic nonnegative $n\times n$ matrix admitting a finite doubly stochastic…
arXiv:2611.08869v1 Announce Type: new Abstract: We resolve the matroid secretary conjecture in its strong form and the single-sample matroid prophet inequality problem, achieving competitive ratios $e$ and $2$,…
arXiv:2611.09600v1 Announce Type: new Abstract: We study coresets for clustering problems, focusing on the classical $k$-median and $k$-means objectives. A coreset is a small weighted summary of the input data that…
arXiv:2611.09172v1 Announce Type: new Abstract: The B+-tree is a ubiquitous search index due to its provable I/O (cache) efficiency. Yet unlike batch-parallel binary search trees, which are both fast and widely…
arXiv:2611.09589v1 Announce Type: new Abstract: Associative arrays and GraphBLAS express sparse computations as matrix operations over a chosen semiring, but the result normally contains only the ordinary value. We…
arXiv:2604.02582v2 Announce Type: replace Abstract: We study the sensitivity of approximation algorithms, which measures how much their output distributions change under a single input edit. We show that, for Set Cover,…
arXiv:2609.01365v2 Announce Type: replace Abstract: In the Shortest Common Superstring problem (SCS), one is given a finite set of strings and is asked to find a shortest string containing every input string as a…
arXiv:2611.09649v1 Announce Type: new Abstract: Ranking vertices by importance is a fundamental task in network mining. The H-index provides such a ranking by asking how many neighbors are themselves well connected; its…
arXiv:2611.08978v1 Announce Type: new Abstract: A recent breakthrough of Kogan and Parter (SODA '22) provided the first polynomial improvement in decades on the size/diameter tradeoff available for shortcut sets.…
arXiv:2611.09447v1 Announce Type: new Abstract: We prove that bin packing is NP-hard to approximate within an additive factor of $o(\ls\OPT)$, even when all item sizes are arbitrarily close to $1/3$. This gives the…
arXiv:2611.09374v1 Announce Type: new Abstract: The Uniform Cost-Distance Steiner Tree Problem asks for a rooted tree that minimizes the connection cost plus a weighted sum of root-to-terminal distances. We develop an…
arXiv:2611.08671v1 Announce Type: new Abstract: Byte-Pair Encoding (BPE) builds a tokeniser by repeatedly merging a most frequent adjacent pair of symbols; its utility is the total reduction in string length achieved by…
arXiv:2611.09071v1 Announce Type: new Abstract: We study vertex-deletion problems on string graphs and, more generally, on graphs excluding a fixed graph as an induced minor. For every fixed graph $H$, fixed nonnegative…
arXiv:2611.09267v1 Announce Type: new Abstract: We study a fundamental load-balancing problem in which $N$ items of strictly positive integer sizes with total size $W$ must be assigned to $B$ bins, with items allowed to…
arXiv:2611.09601v1 Announce Type: new Abstract: We present an algorithm that computes the $p \to q$ norm of a non-negative matrix with $s$ nonzero entries to accuracy $\varepsilon$ in time $\widetilde{O}(s^{3/2} \log…
arXiv:2611.09611v1 Announce Type: new Abstract: Online Timely Bin Packing is a variant of classical online bin packing in which items arrive over time with sizes and deadlines. Packing an item may be deferred until its…
arXiv:2511.16558v3 Announce Type: replace-cross Abstract: We show that a distribution related to Gaussian Boson Sampling (GBS) on graphs can be sampled classically in polynomial time. Graphical applications of GBS…
arXiv:2611.09627v1 Announce Type: cross Abstract: Dallard, Milani\v{c}, and \v{S}torgel, and independently Gartland and Lokshtanov, conjectured that for every planar graph $H$, Maximum Weight Independent Set and List…
arXiv:2602.15815v3 Announce Type: replace-cross Abstract: We study privacy filters, which enable privacy accounting for differentially private (DP) mechanisms with adaptively chosen privacy characteristics. We show that…
arXiv:2611.08570v1 Announce Type: new Abstract: We study the Online Connectivity Augmentation Problem (OCAP) with cut arrivals. In this problem, we are given a $k$-edge-connected graph $G = (V,E)$ with $|V| = n$ and a…
Showing 1 day · 48 items available
