Daily edition · Algorithms
TILens turns technical updates into a focused daily brief: official releases, trusted reporting, and practitioner analysis, deduplicated and organized by topic.
77 articles · 3 sources · 77 papers ·
Top topics: Algorithms · AI
arXiv:2602.23183v2 Announce Type: replace-cross Abstract: We construct a probability distribution, induced by the Perron--Frobenius eigenvector of an exponentially large graph, that cannot be efficiently sampled by any…
arXiv:2610.13937v2 Announce Type: replace Abstract: The arboricity of a graph is the minimum number of forests needed to partition its edges. We present an algorithm that computes the exact arboricity of a simple graph…
arXiv:2611.08416v1 Announce Type: cross Abstract: We develop a new framework for sampling at low temperatures using Glauber dynamics. In this regime, the coexistence of competing modes (commonly referred to as phases)…
arXiv:2611.07369v1 Announce Type: new Abstract: The quickest transshipment problem is a problem defined in a dynamic network with multiple sources and multiple sinks. The goal of this problem is to send all the supplies…
arXiv:2611.08466v1 Announce Type: new Abstract: The canonical cut hierarchy recursively partitions a graph along Tutte-Nash-Williams partitions, choosing the partition with the most number of parts at each step. We give…
arXiv:2609.35555v2 Announce Type: replace Abstract: Correlation clustering has been extensively studied over the last two decades in many different computational models owing to its wide-ranging practical applications.…
arXiv:2611.08143v1 Announce Type: cross Abstract: Monadically dependent graph classes are those in which first-order logic cannot encode all graphs. They include all nowhere dense classes and all classes of bounded…
arXiv:2611.07100v1 Announce Type: cross Abstract: We study the problem of packing a given set of polygons into a minimum-area convex container, that is, placing them without overlap so as to minimize the area of their…
arXiv:2611.05229v2 Announce Type: replace Abstract: We study max-min allocation (the Santa Claus problem) and weighted Nash social welfare for $n$ agents with subadditive valuations over $m$ indivisible items. Using…
arXiv:2609.23947v2 Announce Type: replace Abstract: We study online metric matching with $n$ servers and $n$ requests, all sampled independently and uniformly from $[0,1]^d$. We analyze the Greedy algorithm, which…
arXiv:2611.07308v1 Announce Type: new Abstract: Under the self-referential $K$-SAT exhaustive-search hypothesis (SRK-ESH), no uniform deterministic algorithm computes exact longest common subsequence or standard edit…
arXiv:2611.06957v1 Announce Type: new Abstract: We prove that the integrality gap of the C\u{a}linescu-Karloff-Rabani relaxation for Minimum Multiway Cut is at least $1.2325$ when the number of terminals is large. By a…
arXiv:2611.07043v1 Announce Type: new Abstract: The Steiner shortcut problem asks whether every directed graph $G=(V,E)$ with $n$ vertices and $m$ edges admits an augmentation $G_{+}=(V\cup V_{+},E\cup E_{+})$ with…
arXiv:2611.08114v1 Announce Type: new Abstract: We give a $n^{O(\ell)}$-time algorithm for solving semirandom planted instances of a $k$-ary Boolean constraint satisfaction problem (CSP) with $m \gtrsim…
arXiv:2611.08397v1 Announce Type: new Abstract: We continue the study of the classic \emph{generalized sorting problem}, a basic variant of ordinary sorting. There are $n$ elements and an (initially hidden) total…
arXiv:2611.07248v1 Announce Type: new Abstract: We study how well approximation guarantees for clustering under one norm translate into guarantees under another. Specifically, we compare $k$-clustering in $\mathbb{R}^d$…
arXiv:2511.13056v3 Announce Type: replace-cross Abstract: We study maximin share (MMS) allocations of indivisible goods under nonnegative additive valuations. We give a strongly polynomial-time algorithm that allocates…
arXiv:2611.08351v1 Announce Type: new Abstract: We introduce a new model for dynamic algorithms in which the algorithm has read-only oracle access to a dynamically changing input and random access to its own bounded…
arXiv:2611.08173v1 Announce Type: cross Abstract: Bilateral trade models the task of intermediating between two strategic agents, a seller and a buyer, willing to trade a good for which they hold private valuations. We…
arXiv:2611.08455v1 Announce Type: cross Abstract: We determine the sharp order of discrepancy in Tusn\'ady's problem in every fixed dimension $d\ge 2$. The largest combinatorial discrepancy of $N$ points in…
Showing 1 day · 77 items available
