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.29418v1 Announce Type: new Abstract: We study the active-time scheduling problem with weighted throughput maximization. In this setting, a set of $n$ jobs $J$ arrive at integer release times, each with an…
arXiv:2510.07065v5 Announce Type: replace-cross Abstract: We study the parameterized and kernelization complexity of the \emph{\textsc{$s$-Club Cluster Edge Deletion}} problem, a distance-bounded generalization of…
arXiv:2608.30911v1 Announce Type: new Abstract: A machine faces many jobs whose lengths are hidden. Spending one unit of time to inspect a job may reveal a short job that should be finished now, or it may reveal nothing…
arXiv:1707.09817v2 Announce Type: replace Abstract: We continue research into a well-studied family of problems that ask whether the vertices of a graph can be partitioned into sets $A$ and~$B$, where $A$ is an…
arXiv:2608.23502v2 Announce Type: replace Abstract: Consider the canonical universal hash family $h(x)= ((ax+b)\text{ mod } p)\text{ mod } m$, where $a,b$ are chosen uniformly from $\mathbb Z_p$, which we call linear…
arXiv:2608.30667v1 Announce Type: new Abstract: In this paper, we study the Pattern Avoidance problem of determining whether a given graph $G$ admits a linear vertex order which avoids a given pattern $P$, i.e., a…
arXiv:2608.28767v1 Announce Type: new Abstract: We study the Edge-Constrained Graph Partitioning Problem (ECGP), which asks whether the vertices of a graph can be partitioned into r parts, each inducing at least gamma…
arXiv:2608.31061v1 Announce Type: new Abstract: We study deterministic approximation algorithms for the permanent of a nonnegative matrix through the Bethe permanent, an approximation computable in polynomial time. The…
arXiv:2608.03351v2 Announce Type: replace Abstract: The Lempel-Ziv (LZ) factorization is one of the most fundamental methods for compressing highly repetitive strings, and the number of phrases in its factorization is…
arXiv:2608.30238v1 Announce Type: cross Abstract: Classical lower bounds show that multiplying two degree-three polynomials over $\mathbb F_2$ requires nine scalar products in bilinear or quadratic models. They do not…
arXiv:2511.22803v3 Announce Type: replace Abstract: In this paper, we initiate the study on fault-tolerant (FT) graph spanners for hypergraphs and show the generalization to hypergraphs in the FT setting is non-trivial.…
arXiv:2608.30629v1 Announce Type: cross Abstract: The query-optimal algorithm of [CGWZ26] for general time-dependent Hamiltonian simulation uses $$ q = O\left( \alpha T + \frac{\log(1/\varepsilon)}{\log\left(e +…
arXiv:2608.29274v1 Announce Type: new Abstract: In this paper, we consider an easy greedy approximation algorithm, the good-bad algorithm, introduced by Cou\"etoux for finding a minimum-cost set of edges such that every…
arXiv:2608.03819v2 Announce Type: replace-cross Abstract: A b-coloring is a proper vertex coloring such that every color class contains a vertex, a so-called b-vertex, which sees all colors in its closed neighborhood.…
arXiv:2605.00743v4 Announce Type: replace-cross Abstract: Let $S$ be a set of $n$ points in $\mathbb{R}^2$. Our goal is to preprocess $S$ to efficiently compute the smallest enclosing disk of the points in $S$ that lie…
arXiv:2608.29180v1 Announce Type: cross Abstract: We study the approximability of rank aggregation under the Ulam metric. In the \emph{Ulam median} problem, the goal is to find a permutation minimizing the sum of its…
arXiv:2607.27829v2 Announce Type: replace Abstract: We give a deterministic $(1.3865+\epsilon)$-approximation for correlation clustering on complete graphs, improving the previous best factor of $1.485+\epsilon$ of Cao…
arXiv:2608.30299v1 Announce Type: new Abstract: We present a new distributed algorithm for computing a minimum spanning tree (MST) in the \textsf{CONGEST-KT$_{1}$} model, where messages are limited to $O(\log n)$ bits…
arXiv:2608.16947v2 Announce Type: replace Abstract: Dynamic Mixture-of-Experts Serving allocates k replica GPUs among m experts as workloads change. At each round, the online algorithm sees the current workload, chooses…
arXiv:2608.29503v1 Announce Type: cross Abstract: Worst-case online classification is governed by sequential complexity, such as Littlestone dimension, and can be impossible even for statistically simple classes, such…
Showing 1 day · 61 items available
