CS Paper Radar

Exact and Asymptotic Analysis of Greedy Online Facility Assignment on Cycle Metrics

Md. Tanzeem Rahat, Md. Rawha Siddiqi Riad, Md. Manzurul Hasan

cs.DS ·submitted 2026-10-11 17:01 UTC · v1
theory

Abstract

We identify the free-facility gaps of greedy online assignment on a cycle with the discrete additive coalescent and use this connection to determine the exact expected assignment cost. The cycle has circumference $n$, with one unit-capacity facility at each integer point and $n$ independent uniform arrivals. Each request is assigned immediately to a nearest free facility. The conditional one-step cost is the sum of squared gap lengths divided by $4n$. A uniform cyclic-order argument identifies the unordered gap process with additive coalescence. The classical Cayley-tree representation then reduces the accumulated cost to a two-vertex distance functional, yielding \[ G_n=\frac n4\sum_{d=0}^{n-1}\prod_{j=1}^{d}\left(1-\frac jn\right) \sim\frac14\sqrt{\frac\pi2}\,n^{3/2}. \] The formula requires a linear number of scalar recurrence steps to evaluate. We also obtain an asymptotic upper bound of $π\sqrt3/2$ on the ratio of expected greedy cost to expected offline optimum under this arrival model. An exact rational Bellman calculation shows that greedy is optimal for three facilities but exceeds the optimal online expected cost by $1/512$ for four facilities. Independent exact recurrences and finite tree enumeration provide reproducible checks of the analysis.

Closest papers

Nearest neighbours by meaning across the whole index.

Metric Facility Location under Batched Random Order

cs.DS ·2026-11-03 ·Fabrizio Grandoni, Stefano Leonardi, Matteo Russo
theory similarity 0.64
Abstract

We study online metric facility location in the batched random-order model. An adversary partitions $n$ clients into $B$ nonempty batches, which arrive in uniformly random order. Each batch is revealed in full, and its clients must be connected to open facilities before the next batch arrives. Openings and assignments are irrevocable, and the objective is to minimize the total opening and connection cost. For both uniform and nonuniform opening costs, we prove that the tight competitive ratio is \[ Θ\!\left(\min\left\{\log(B+1), \sqrt{\log(n-B+2)}\right\}\right). \] Thus, the ratio is constant both when there is a single batch and when every batch is a singleton, but intermediate numbers of batches can require a $Θ(\sqrt{\log n})$ ratio. Our algorithms build on Meyerson's algorithm (2001) and do not need to know $n$ nor $B$. A key algorithmic novelty is that we process the clients in a batch one by one in uniform random order (hence neglecting the global properties of the batch). We present a novel analysis of this algorithm that hinges on the random order of the batches, as well as of the clients within each batch. We also provide a matching competitive ratio lower bound already for uniform costs, and even when the entire metric is known in advance.

0.21

Online Network Design with Maximum Delay and Stochastic Arrivals

cs.DS ·2026-11-10 ·Tianhang Lu
theory similarity 0.62
Abstract

We study online network services that combine pending requests into batches. Each batch pays for its spatial service and for the waiting time of its oldest request. The objective is the sum of these costs over all batches. Thus requests can share both a spatial purchase and one maximum-delay charge. We assume independent Poisson arrivals of known rates, while actual requests are revealed only upon arrival. For stateless services, suppose that each type has an attainable minimum cost when served alone, that every batch costs at least the stand-alone minimum of each type it contains, and that one finite-cost action can serve any batch, regardless of its request multiplicities. We give a deterministic algorithm with long-run ratio of expectations $e/(e-1)$ against an unrestricted offline optimum. This factor is optimal, even allowing randomization, already at one request location. The key comparison measures the union of time intervals associated with requests. The theorem applies directly to multi-root and pair aggregation on trees. We also study facility location, where each request pays its own connection distance and the bounded-action assumption can fail. A deterministic policy gives a ratio $3$ for arbitrary nonnegative opening costs. It immediately serves a finite initial set of requests, computes an assignment from their observed arrival gaps, and then keeps that assignment fixed. Its analysis combines Poisson insertion with a time-slice packing bound on the offline optimum. Every guarantee includes the full cost of completing finite inputs without an end-of-input signal.

0.15

Parameterized Complexity and Geometric Approximation of Riesz Energy Subset Selection

cs.CG cs.CCcs.DS ·2026-11-10 ·Michael Emmerich, Soumen Atta
code/data similarity 0.62
Abstract · 35 pages, 6 figures. Code, data, and instructions for reproducing the experiments: https://github.com/emmerichmtm/PCGA-Riesz

We choose $k$ of $n$ sites to minimize Riesz $s$-energy, in which a pair at distance $t$ contributes $t^{-s}$. For $s=2$, exact selection is polynomial on a line but NP-hard in the plane. Adapting the proxy lemma of Ceccarello et al. gives an efficient parameterized approximation scheme (EPAS) for fixed Euclidean dimension and fixed $s>0$. To sharpen the bound, we start with a geometric packing. Farthest-first traversal gives $2k$ centers separated by at least the last insertion distance $r$. If one site of an optimum is removed, each of the $k-1$ remaining sites excludes at most one center closer than $r/2$, leaving at least $k+1$ centers free. The new step is a discrete exchange bound: the removed site's interaction energy is at most the average it would contribute at those free centers. In the plane at $s=2$, this reduces the representative bound from $O(k^2\log(2k)/\varepsilon^2)$ for a packing estimate of total energy to $O(k\log(2k)/\varepsilon^2)$, independently of $n$. Rational planar examples show that the resulting separation scale $r/\sqrt{\log(2k)}$ is sharp. A $(1+\varepsilon)$ approximation on rational planar sites takes $O(nk+n\log n)+(C\log(2k)/\varepsilon^2)^k$ operations of polynomial bit cost. The observed number $M$ of representatives determines the search size $\binom{M}{k}$. With one million sites, $k=5$ and $\varepsilon=1/2$, the exchange grid left 252 subsets on clustered inputs and about $9.3\times10^{26}$ on uniform inputs. The method extends to metrics of bounded doubling dimension and to compact domains with effective geometric routines, including filled simple polygons. At $s=2$, exact decision on metrics with nonzero distances in $\{1,2\}$ is W[1]-complete in $k$. A gap that shrinks with $k$ rules out a deterministic EPAS on unrestricted metrics unless FPT = W[1].

0.49

A 2.37332-Competitive Algorithm for Online Square Packing with Gravity

cs.CG ·2026-09-09 ·Nichlas Langhoff Rasmussen
theory similarity 0.61
Abstract · 13 pages. 5 figures

We consider online packing of axis-parallel squares into a unit-width strip under the Tetris and gravity constraints: An incoming square must be lowered from above along a monotonic downwards path until it reaches support from below. Fekete, Kamphans, and Schweer [Algorithmica, 2014] gave an algorithm with asymptotic competitive ratio $34/13\approx2.6154$ in this model. We present $\mathrm{AsymmetricSlots}$, a recursive algorithm based on splitting each slot into a wide and narrow subslot. The proof uses a local charging argument: squares that are large relative to its associated slot pay for the height they create with their own area, while smaller squares are balanced between the two subslots and may use a bounded temporary credit. For a suitable split parameter $p^\star$, we prove $\mathrm{AsymmetricSlots}{p^\star}(σ)\le 2.37332 \operatorname{OPT} (σ)+O(1)$ for every input sequence $σ$. Additionally, we show that the same framework gives an algorithm with asymptotic competitive ratio $O(κ)$ for rectangles of aspect ratio at most $κ$, and a matching $ Ω(κ)$ lower bound shows that the dependence on $κ$ is asymptotically optimal. For the square algorithm, we give a lower bound of $2$ on its asymptotic competitive ratio.

0.33

Optimal Online Weighted Connectivity Augmentation

cs.DS ·2026-10-30 ·Mohit Garg, Felix Hommelsheim, Alexander Lindermayr
theory similarity 0.61
Abstract · 32 pages, 12 figures

In the online Weighted Connectivity Augmentation Problem (WCAP), we are given a $k$-edge-connected graph on $n$ vertices and a set of additional edges, called links, with nonnegative costs. Pairs of vertices arrive one by one, and an online algorithm must immediately and irrevocably buy links so that each pair becomes $(k+1)$-edge-connected. The goal is to minimize the total cost of the purchased links. We obtain a deterministic polynomial-time $O(\log n)$-competitive algorithm for WCAP, improving the previous $O(\log^2 n)$ bound (SODA 2026). Our bound is asymptotically optimal, even for randomized algorithms in the random-order model. The general problem reduces to the case where the underlying graph is a cycle, for which link costs in $\{0,1\}$ already yield an $Ω(\log n)$ lower bound. Surprisingly, for unit costs on a cycle, we obtain a deterministic polynomial-time $4$-competitive algorithm, improving the previous $O(\log n)$ bound (SODA 2026), and prove that this ratio is optimal among deterministic algorithms. Thus, with unit costs, cycles are easier than trees, where the optimal competitive ratio is $Θ(\log n)$.

0.25

The Online $k$-Taxi Problem Is Competitive on All Metrics

cs.DS ·2026-11-04 ·Christian Coester, Yichen Huang, Tze-Yang Poon
similarity 0.60
Abstract

The online $k$-taxi problem is a natural generalization of the $k$-server problem: $k$ taxis must serve a sequence of requests in a metric space. Each request is a pair of points $(r,s)$, and the algorithm serves the request by first moving a taxi to $r$ (to pick up a passenger) and then to $s$ (to drop off the passenger). The cost is the total distance traveled by the taxis without a passenger. Previous bounds for general $k$ all depended on the number of points $n$ or the aspect ratio $Δ$ of the metric space, both of which can be infinite on general metrics, and competitive algorithms were previously known on general metrics only for $k \le 3$. In this work, we give a $9^{k-1}$-competitive randomized algorithm against adaptive online adversaries and, as a corollary, an $81^{k-1}$-competitive deterministic algorithm for the online $k$-taxi problem.

0.10

Traveling Salesman Problem on Graphs with Proportional Independent Set

cs.DS math.CO ·2026-10-30 ·Ethan X. Fang, Shengtao Guo, Junwei Lu, Yuan Yao
similarity 0.60
Abstract · 13 pages, 2 figures

We give a deterministic algorithm for minimum-cost Hamiltonian cycle in undirected graphs with arbitrary real edge costs and an independent set of size at least $αn$, for any fixed $3/7<α\le1/2$. It runs in $O^*(γ(α)^n)$ time for an explicit constant $γ(α)<2$; for bipartite graphs, the bound is $O^*((1+2\sqrt2)^{n/2})\approx O^*(1.957^n)$. The algorithm is based on a restricted Held--Karp dynamic program. Its state enumeration uses structural properties of minimum-cost assignments arising from a regular triangulation of a product of simplices.

0.16

Online Vertex Connectivity Augmentation

cs.DS ·2026-11-11 ·Yaowei Long, Sepideh Mahabadi, Jakub Tarnawski
similarity 0.60
Abstract · 35 pages

Network design problems form a classic subfield of online algorithms, but almost nothing is known about their more challenging vertex-connectivity variants. We initiate the study of online vertex-connectivity network design for arbitrary demand pairs by considering the fundamental problem of connectivity augmentation. In an instance of \emph{Online Vertex Connectivity Augmentation} (OVCA), we are given a $k$-vertex-connected graph $F$ and a set of additional purchasable edges (with costs). Demand pairs $(s_1,t_1),(s_2,t_2),\dots$ then arrive online. Upon each arrival, the algorithm must irrevocably purchase edges so that $s_i$ and $t_i$ become $(k{+}1)$-vertex-connected in the union of $F$ with all edges purchased so far. Our main contribution is an $O((k+\log n)\log n)$-competitive online algorithm for OVCA. We also give an offline $O(k+\log n)$-approximation algorithm. We obtain our algorithms via a structural dichotomy on the minimum vertex cuts of $F$. We note that some dependence on $k$ in the approximation ratio is necessary -- i.e., the problem is hard to approximate within any $\mathrm{polylog}(n)$ factor independent of $k$ -- which shows a separation from the edge-connectivity setting. Finally, specializing to $k=1$, our methods yield the first polylogarithmic-competitive online algorithm for a vertex-connectivity survivable network design problem, namely an $\widetilde O(\log^3 n)$-competitive algorithm for online $\{1,2\}$-VC-SNDP (i.e., an SNDP variant where each demand pair comes with a vertex-connectivity requirement of $1$ or $2$).

0.18