CS Paper Radar

Local decisions, diffusive influence, and lower bounds for graphical balanced allocation

Obinna Okechukwu

cs.DS math.PR ·submitted 2026-09-30 01:00 UTC · v2
theorycode/data

Abstract

In graphical two-choice allocation, each arriving ball is assigned to one endpoint of a random edge. We study rules whose decision is a monotone function of the two endpoint loads, allowing edge-dependent thresholds and fresh randomization. Such a rule has an exact unit-discrepancy coupling: adding one ball to the initial state produces one tagged discrepancy at every later time. We represent the tag by conditional-expectation projections on the marked edge space and obtain diffusive displacement bounds. A transport-volume inequality then converts slow propagation of influence into lower bounds for the load gap. On the cycle with $n$ vertices, from every initial distribution and at every physical time $t\ge 1/n$, the expected gap is at least a constant times $\min\{\sqrt n,t^{1/4}\}$, and the gap exceeds this scale with probability at least $1/8$. After exactly $k\ge1$ allocations, the corresponding scale is $\min\{\sqrt n,(k/n)^{1/4}\}$. No stationarity, symmetry, recurrence, or moment assumption is used. A smoothed threshold rule in the same class has expected gap $O(\sqrt n\log n)$ up to any fixed polynomial time horizon, so the saturated cycle bound is sharp within the class up to a logarithmic factor. The general inequality also yields a lower bound of order $\sqrt{L/K}$ on the $L\times K$ rectangular torus $C_L\square C_K$; combined with a strategy-independent logarithmic bound, this gives order $\sqrt{L/K}+\log(LK)$. These results separate endpoint-local rules from global-information strategies that achieve polylogarithmic gaps on cycles. All numbered results are verified in Lean.

Comment
28 pages, 2 figures. All numbered results are formalized in Lean 4: https://github.com/obinnaokechukwu/cycle-gap-lowerbound-lean

Closest papers

Nearest neighbours by meaning across the whole index.

Sharper Bounds for Graphical Two-Choice Allocation

cs.DS math.PR ·2026-11-01 ·Obinna Okechukwu
benchmarktheory similarity 0.70
Abstract · 28 pages, 5 figures

In graphical two-choice allocation, vertices are bins, and each arriving ball must be placed irrevocably at one endpoint of a uniformly random edge. The objective is to keep the maximum-minus-minimum load gap small at every time. On cycles, endpoint-local monotone rules incur polynomial gaps at long time horizons, whereas global rules can achieve polylogarithmic gaps. We prove a joint exponential-moment inequality for the orthogonal contrasts of a binary partition tree, controlling all contrasts along a root-to-leaf path simultaneously. Applied to the Bansal--Feldheim strategy, it improves the gap on every $κ$-edge-connected $d$-regular graph from $O((d/κ)\log^4 n\log\log n)$ to $O((d/κ)\log^3 n\log\log n)$. We give an explicit strategy on the $n$-cycle with expected gap $O(\log^2 n)$ uniformly over deterministic times and exponential tails at each such time. An Euler-tour projection yields $O(\bar d\log^2(2M))$ for every connected graph with $M$ edges and degree-proportional capacities. For lower bounds, we introduce a stochastic cut workload: the expected largest normalized overload forced by the requests, plus an indivisibility term. For every online integral strategy, the supremum over time of the expected gap is at least one sixth of this benchmark. Regular rings of cliques attain $Ω((d/κ)\log n)$ along an explicit family, improving the prior additive lower bound. With unequal capacities, the workload need not control the gap: one family has constant relative cut slack, bounded workload and gap $Ω(\log\log n)$; another has workload at most $20$ but forces gap $Ω(\log n)$ even for clairvoyant fractional allocations that remain irrevocable.

0.22

Logarithmic Embeddings into Probabilistic Spanning Trees for Distances and Capacities

cs.DS ·2026-11-03 ·Mohammad Hajiaghayi
theory similarity 0.63
Abstract

We prove that every connected $n$-vertex graph admits a probabilistic embedding into its spanning trees with expected distance stretch $O(\log n)$. This settles the logarithmic stretch conjecture of Alon, Karp, Peleg, and West, whose spanning-tree game appeared at the 1991 DIMACS Workshop on On-Line Algorithms and in SIAM Journal on Computing in 1995. A weighted form of the theorem also yields a distribution over spanning trees with capacities exactly equal to their fundamental graph cuts. Every tree dominates every graph cut, every cut is approximated within $O(\log n)$ in expectation, and the same capacity distribution defines an $O(\log n)$-competitive fractional oblivious routing. The distance and capacity distributions may differ. Diamond graphs give matching logarithmic lower bounds for stretch, congestion, and cut distortion. For rational input, both distributions are constructed deterministically in polynomial time and use at most $m$ trees, where $m$ is the number of graph edges. We prove an $Ω(m/ρ)$ support lower bound for congestion $ρ$; in particular, $(1-o(1))m$ trees can be necessary for near-unit congestion, even when the optimum tends to one. Thus linear dependence on $m$ is unavoidable in this regime. The weighted theorem combines a protected-geodesic petal decomposition with a pathwise entropy bound for locally selected centers. A local averaging inequality derandomizes the radii, and an adaptive rational packing procedure constructs the distributions.

0.54

The Kemeny-Braess Paradox in Random Graphs

cs.DM math.COcs.SImath.PR ·2026-10-16 ·Manuel Bodirsky, Lorenzo Ciardo, Mihyun Kang
similarity 0.61
Abstract

In 2016, Kirkland and Zeng initiated the mathematical treatment of Braess paradox for random walks on graphs using Kemeny's constant as the measure of travel time. We study this phenomenon for the Erdős-Rényi random graph $G(n,p)$. An edge in a connected graph is called Kemeny-Braess if its deletion preserves connectedness and decreases Kemeny's constant, while a nonedge is Kemeny-Braess if its insertion increases Kemeny's constant. Let $\bar d=(n-1)p$ be the expected degree of $G\sim G(n,p)$, and assume that $\bar d-\log n\to\infty$, so that $G$ is connected with high probability. We determine the sharp asymptotic thresholds for the existence of both types of paradoxical behaviour. With $C^*=1/(1-\log 2)$, the threshold for Kemeny-Braess edges is $\bar d=C^*\log n$, whereas the threshold for Kemeny-Braess nonedges is $\bar d=2C^*\log n$. Hence, as the expected degree $\bar d$ increases, the connected regime exhibits three phases: first Kemeny-Braess paradox occurs for both edges and nonedges, then only for nonedges, and finally it disappears. In particular, in the dense regime, with high probability $G$ has no Kemeny-Braess edges or nonedges. This contrasts sharply with the spectral gap of the normalised Laplacian, for which Braess' paradox persists at constant edge density. Our proof combines a spectral-moment expansion of Kemeny's constant with uniform edge-perturbation estimates. Near the thresholds, the sign of the perturbation is governed by the endpoint degrees, and binomial large deviations yield the constant $C^*$ and the factor of two between the two thresholds.

0.29

Budget-Independent Influence Maximization in Nearly Linear Time

cs.DS cs.SI ·2026-09-20 ·Zhijie Zhang
similarity 0.61
Abstract

Influence maximization asks for $k$ seed vertices that maximize the expected spread of a diffusion process in a network. Standard near-optimal-time algorithms based on reverse-reachable sampling achieve a $(1-1/e-\varepsilon)$ approximation, but their expected running-time bounds grow linearly with the seed budget $k$. We remove this multiplicative dependence: for the independent cascade model, our algorithm succeeds with probability at least $1-δ$ in $O((m+n)\varepsilon^{-3}\log(2n/δ))$ expected time. The result extends to triggering models with explicitly charged local sampling costs. We reserve $O(\varepsilon k)$ seed positions for cost-weighted random vertices, allowing reverse-reachable searches to stop as soon as they encounter a reserved seed. An independent sample-count estimation phase uses a statistic that also controls the expected search cost. Matching these quantities eliminates the multiplicative dependence on $k$ while preserving the approximation guarantee.

0.38

Large independent sets via neighborhood block dynamics, Glauber dynamics, and local occupancy

cs.DS math.CO ·2026-11-02 ·Ewan Davies, Brian Tan
similarity 0.61
Abstract · 28 pages

Local occupancy can be used to bound the expected size of a hard-core independent set. The framework of locally stationary distributions shows that for triangle-free graphs, despite slow mixing at the relevant fugacity parameter, standard Glauber dynamics can be used to find sets close to the local occupancy guarantee. We improve the application of this framework to the hard-core model by replacing a conditional mixing argument with a more direct approach based on a short sequence of single-site updates that, from every initial configuration, achieves the required occupancy inequality. In general graphs, naive conditional mixing estimates or certain problematic structures in the neighborhood can in principle incur running time cost exponential in the maximum degree $Δ$. We design short update sequences that, via our relaxed criterion, yield running times polynomial in $Δ$ for graphs with a hereditary bound $b$ on the density of $K_{t,t}$ subgraphs in neighborhoods. Our methods handle the case where $t$ and $b$ can grow with the maximum degree, and the resulting algorithm attains the random graph shattering threshold when they grow sufficiently slowly. That is, we give improved local occupancy parameters and a short update sequence analysis which together show that Glauber dynamics finds independent sets of size $(1-o(1))n(\logΔ)/Δ$ in time polynomial in $n$ and $Δ$ whenever $t$ and $b$ are constant or grow suitably slowly. In a similar regime, we also establish that the (correspondence) chromatic number is at most $(1+o(1))Δ/\logΔ$ which improves upon prior results by a factor of at least $4$ in the case $t\ge 4$.

0.35

Smoothed Analysis for Distributed MIS

cs.DC ·2026-11-12 ·Dipan Dey, Fabien Dufoulon, William K. Moses, Gopal Pandurangan
theory similarity 0.60
Abstract

We study smoothed analysis of the distributed Maximal Independent Set (MIS) problem. Luby's algorithm computes an MIS in $O(\log n)$ rounds, while the recent $Ω(\log n/\log\log n)$ lower bound of Khoury and Schild (2026) shows that it is nearly optimal even in the LOCAL model. We ask whether small random perturbations can overcome this worst-case barrier. Given an arbitrary base graph $G$ on $n$ nodes, we consider the smoothed graph $\mathcal{G}_s=G\triangle G(n,p)$, where $G(n,p)$ is an independent random graph and $\triangle$ denotes symmetric difference. Thus, each possible edge is independently toggled with probability $p$. We establish nearly tight bounds on the smoothing needed for faster distributed MIS. For every base graph $G$, when $p=β\ln n/n$ for a sufficiently large constant $β$, a randomized LOCAL algorithm, given only $\mathcal{G}_s$, computes an MIS of $\mathcal{G}_s$ in $O(\sqrt{\log n})$ rounds with high probability. This is almost quadratically faster than the worst-case lower bound. Conversely, if $p\le(1/2-δ)\ln n/n$ for a fixed constant $δ>0$, there exists a base graph on which every randomized LOCAL MIS algorithm requires $Ω(\log n/\log\log n)$ rounds on the smoothed graph. Hence, the smoothing parameter required for this speedup is optimal up to a constant factor. These results show that smoothed analysis can overcome worst-case lower-bound barriers for distributed local graph problems.

0.10

Approximation and Inapproximability of Non-Preemptive Dial-a-Ride

cs.DS ·2026-10-21 ·Jingyang Zhao, Mingyu Xiao
similarity 0.59
Abstract

The non-preemptive dial-a-ride problem (DaRP) asks for a minimum-cost route of a capacitated vehicle that serves a collection of pickup-and-delivery requests, without allowing objects to be transferred or temporarily unloaded. We study this problem and the closely related minimum-ratio Steiner $k$-Forest (S$k$F) in general symmetric metrics on $n$ locations. We develop a randomized polynomial-time algorithm with expected approximation ratio $\mathcal{O}(n^{1/4}\log^{11}n)$ for the minimum-ratio S$k$F. Our algorithm combines a deterministic approximation on hierarchically well-separated trees with randomized metric embeddings. Using this algorithm, we obtain expected $\mathcal{O}(n^{1/4}\log^{12}n)$-approximations for both the non-preemptive DaRP and the S$k$F. These guarantees improve on the previous $n^{0.3+\varepsilon}$-approximation ratios for the S$k$F and the non-preemptive DaRP, where $\varepsilon>0$ is any fixed constant. Complementing these algorithmic results, we establish the first superconstant inapproximability bounds for the non-preemptive DaRP. Under the Exponential Time Hypothesis (ETH), no deterministic polynomial-time algorithm achieves an $x^{1/(\log\log x)^c}$-approximation for some constant $c>0$, where $x$ denotes either the number of locations $n$ or the vehicle capacity $k$. Under the quantitative Gap-ETH, we rule out every deterministic polynomial-time $x^{o(1)}$-approximation. These bounds hold even on unit-edge stars with $n=(2+o(1))k$.

0.21

Deterministic Girth Approximation in Weighted Undirected Graphs

cs.DS ·2026-10-09 ·Avi Kadria
similarity 0.59
Abstract

We give deterministic algorithms for approximating the girth~$g$ of an undirected graph with $n$ vertices, $m$ edges, and nonnegative real edge lengths. For every integer $k\geq2$, our algorithm returns a cycle of length at most $\frac{2k}{3}g$ in $O((m+n^{1+2/k})k\log n)$ worst-case time. For every constant~$k$, this matches the stretch and the expected running time of the randomized algorithms of Kadria, Roditty, Sidford, Vassilevska Williams, and Zwick [SODA'23, SICOMP'26] and Kadria, Roditty, and Vassilevska Williams [ESA'26]. In general, it loses only a factor of $O(\min\{k,\log n\})$ in the term that depends on~$m$. The best previous deterministic trade-off, of Kadria, Roditty, Sidford, Vassilevska Williams, and Zwick [SODA'22], has stretch~$k$ instead of $\frac{2k}{3}$ at the same exponent (for even~$k$) and requires integer edge lengths. In particular, for $k=3$ we obtain a deterministic $2$-approximation in $O((m+n^{5/3})\log n)$ time for real edge lengths, whereas the deterministic algorithm of Ducoffe [SIDMA'21] for real lengths has stretch $2+\varepsilon$. Our main technical idea is that a deterministic construction of the Thorup--Zwick hierarchy used by these algorithms may stop exploring as soon as it finds a cycle: the approximation analysis only needs clusters truncated at half the best cycle certificate found, so balls stopped in this way need not be hit. Together with a degree-weighted selection rule, this bounds the work of each level by its number of edges and stored ball entries. More generally, a ball need not be hit whenever the analysis only uses clusters up to a radius bounded by a certificate that the algorithm has already found.

0.44