Daily edition · Algorithms
TILens turns technical updates into a focused daily brief: official releases, trusted reporting, and practitioner analysis, deduplicated and organized by topic.
38 articles · 3 sources · 38 papers ·
Top topics: Algorithms · AI
arXiv:2406.00437v4 Announce Type: replace Abstract: In the Stable Roommates problem, we seek a stable matching of the agents into pairs, in which no two agents have an incentive to deviate from their assignment. It is…
arXiv:2609.02498v1 Announce Type: new Abstract: Navigability is a fundamental property of graph-based search structures and plays an important role in the analysis of nearest-neighbor algorithms. Informally, a graph is…
arXiv:2607.17287v2 Announce Type: replace Abstract: The suffix array ($\SA$) and inverse suffix array ($\ISA$) are fundamental data structures in string algorithms. For a text $T[0 \dd n)$ over an alphabet $[0 \dd…
arXiv:2609.01949v1 Announce Type: new Abstract: A layout of a graph G is an injective function $f : V(G) \rightarrow Z$, and the bandwidth of a layout f is $bw(G,f) = max_{uv \in E(G)} |f(u) - f(v)|$. The bandwidth…
arXiv:2609.02388v1 Announce Type: new Abstract: We study the low-degree Steiner forest decomposition. Given a graph $G=(V,E)$ and a terminal set $U\subseteq V$, the standard decomposition returns a set $X\subseteq V$ of…
arXiv:2608.11057v2 Announce Type: replace Abstract: We study the minimum-weight mixed dominating set problem on threshold graphs. In this problem, vertices and edges have weights, and the goal is to find a mixed set of…
arXiv:1911.01951v4 Announce Type: replace Abstract: The Bron-Kerbosch algorithm is a well known maximal clique enumeration algorithm. So far it was unknown whether it was output sensitive or not. In this paper we…
arXiv:2606.06686v2 Announce Type: replace-cross Abstract: This paper presents a simple framework that settles the complexity of Multi-Agent Path Finding (MAPF) on trees across standard objectives - distance, makespan,…
arXiv:2609.02017v1 Announce Type: cross Abstract: For an $n\times n$ nonnegative matrix $A$, the Bethe permanent, which is computable in deterministic polynomial time, satisfies the tight universal comparison…
arXiv:2609.02764v1 Announce Type: new Abstract: This paper presents a new randomized algorithm for solving the exact shortest vector problem. For the $n$-dimensional lattice $\mathcal L$, our algorithm runs in time and…
arXiv:2408.04920v2 Announce Type: replace Abstract: Two words $x,y$ of the same length are said to be \emph{parameterized equivalent} if there exists a character bijection that transforms $x$ into $y$. A word $w$ is…
arXiv:2602.10851v2 Announce Type: replace-cross Abstract: Stable matching is a fundamental area with many practical applications, such as centralised clearinghouses for school choice or job markets. Recent work has…
arXiv:2609.02851v1 Announce Type: new Abstract: Temporal graphs model dynamic networks by assigning positive integer time labels to the edges, while information propagates along temporal paths, whose edge labels are…
arXiv:2609.02124v1 Announce Type: new Abstract: Let $G\in\mathbb{R}^{M\times N}$ have independent standard Gaussian entries. For a fixed margin $\kappa\in\mathbb{R}$, the asymmetric binary perceptron asks for…
arXiv:2505.11456v3 Announce Type: replace Abstract: We study the Stable Fixtures problem, a many-to-many generalisation of the classical non-bipartite Stable Roommates matching problem. Building on the foundational work…
arXiv:2409.00771v4 Announce Type: replace Abstract: In this work, we study the task of scheduling jobs on a single machine with sequence dependent family setup times under the goal of minimizing the makespan, that is,…
arXiv:2601.14195v2 Announce Type: replace-cross Abstract: Stability is crucial in matching markets, yet in many real-world settings - from hospital residency allocations to roommate assignments - full stability is…
arXiv:2609.01682v1 Announce Type: cross Abstract: Albertson conjectured that every graph with chromatic number r has crossing number at least cr(K_r). The conjecture was verified for r <= 12 by Albertson, Cranston and…
arXiv:2609.02080v1 Announce Type: cross Abstract: The basis number $\mathrm{bn}(G)$ of a graph $G$ is the minimum edge-congestion of a basis of its cycle space. We prove that every finite $n$-vertex multigraph satisfies…
arXiv:2512.06878v2 Announce Type: replace-cross Abstract: In this paper, we characterize finite graphs with circular chromatic number less than 3 in terms of the existence of certain signings ($\mathbb Z_2$-labellings…
Showing 1 day · 38 items available
