CS Paper Radar

Stochastic Network Speed Scaling with Competitive Ratios Independent of the Network

Yash Khanna

cs.DS cs.PF ·submitted 2026-10-02 16:47 UTC · v2
theory

Abstract

In network speed scaling, jobs arrive over time at a network of servers whose speeds can be tuned, every job must be processed by the servers along one of its allowed routes, and the goal is to minimize the total flow time plus the total energy. For stochastic arrivals, the competitive ratio of Vaze and Nair depends on the network, through the lengths of the routes it uses. We show that this dependence can be removed: we give an algorithm, which routes the jobs by solving a convex program and runs every server at a fixed speed, whose competitive ratio depends only on the power functions; for $P(s)=s^2$, it is at most the golden ratio $\varphi\approx1.618$. The key idea is a lower bound on the optimal cost which, like the cost of our algorithm, is a sum over the servers of a function of each server's load, so the analysis reduces to a single server. We also show that the routing rule of Vaze and Nair can be a factor $Ω(L)$ away from optimal, where $L$ is the length of the longest route.

Comment
14 pages, 2 figures, 1 table

Closest papers

Nearest neighbours by meaning across the whole index.

Online Survivable Network Design with Arbitrarily Small Connectivity Loss

cs.DS ·2026-11-12 ·MohammadTaghi Hajiaghayi, Saeed Seddighin
similarity 0.60
Abstract

In the online survivable network design problem, a graph with edge costs is known in advance, and requests arrive one at a time. Each request is a pair of vertices $(s,t)$ with a connectivity requirement $k$, and the algorithm must irrevocably buy edges so that $s$ and $t$ are joined by $k$ edge-disjoint paths. The goal is to keep the total cost close to that of an optimal offline solution. Gupta, Krishnaswamy, and Ravi~\cite{GKR12} obtain an $O(k\log^3 n)$-competitive algorithm, where $k$ is the maximum requirement, without relaxing the connectivity requirement. Dehghani, Ehsani, Hajiaghayi, Liaghat, and Seddighin~\cite{DEHLS18} obtain a polylogarithmic competitive ratio when the connectivity requirement is allowed to be relaxed by a factor of $2+\varepsilon$. We show that relaxing the connectivity requirement by a factor of only $1+\varepsilon$ suffices to obtain a polylogarithmic competitive ratio.

0.19

Online Network Design with Maximum Delay and Stochastic Arrivals

cs.DS ·2026-11-10 ·Tianhang Lu
theory similarity 0.59
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.14

The Harmonic Online $k$-Server Algorithm Is Poly(k)-Competitive

cs.DS ·2026-11-03 ·Yichen Huang
theory similarity 0.59
Abstract

The online $k$-server problem is one of the most fundamental problems in online algorithms. In this problem, $k$ servers are located in a metric space and serve a sequence of requests at points in the metric space by moving a server there. The Harmonic algorithm is a very natural algorithm: it chooses a server with probability inversely proportional to its distance from the request. It is also highly efficient, being memoryless and answering each request in $O(k)$ time. However, its competitive ratio has remained unsettled between the $O(2^k \log k)$ upper bound (Bartal and Grove, JACM 2000) and the $k(k+1)/2$ lower bound (Raghavan and Snir, 1994, IBM J. Res. Dev.). We prove that Harmonic is $2k^4$-competitive on every metric space against adaptive online adversaries. Our analysis uses a potential combining corrected electrical energy with the distances of online servers to their assigned adversary locations.

0.11

Tight Bounds for Randomized Generalized $k$-Server on Uniform Metrics

cs.DS ·2026-10-27 ·Junho Hwang
theory similarity 0.58
Abstract · 24 pages, 3 figures

In the generalized $k$-server problem, each of $k$ servers moves in its own metric space, and a request $(r_1,\dots,r_k)$ is served once some server $i$ stands at the point $r_i$ of its space. We determine the randomized competitive ratio against an oblivious adversary when every space is a uniform metric. With unit distances the ratio is $Θ(k\log k)$: we give a $(k+1)\ln(2k)$-competitive algorithm and show that for large $k$ every algorithm has ratio at least $\frac{1}{20}k\ln k$, improving the bounds $O(k^2\log k)$ and $Ω(k)$ of Bienkowski, Jeż, and Schmidt. When server $i$ pays $w_i$ per move, the ratio is $\exp(Θ(k))$: we give a $20^k$-competitive algorithm, which also applies to weighted $k$-server on uniform metrics. This improves the $\exp(O(k^2))$ bound of Bijoy, Mondal, and Chiplunkar and matches the $Ω(2^k)$ lower bound of Ayyadevara and Chiplunkar up to the base of the exponent. Both algorithms follow normalized weights exactly, through couplings whose expected movement is controlled by the decrease of the logarithm of the total weight. The lower bound hides a random permutation among the solutions of random permutation constraints, which split into small, well-separated components, and then forbids one position to one server at a time.

0.34

Approaching Optimal Scaling of Queue Size for an Input-Queued Switch

cs.PF math.PR ·2026-10-27 ·Taha Ameen, Weina Wang
similarity 0.58
Abstract

We study the scaling of the expected total queue length in an $n\times n$ input-queued switch. It has been conjectured that the optimal scaling is $O(n/(1-ρ))$, up to logarithmic factors, where $ρ$ is the system load. This conjecture has been established in the traditional heavy-traffic regime and in certain sub-regimes of the large-system regime. But it remains unresolved over a wide range of load scalings in the large-system regime. In this paper, we develop a family of scheduling policies parameterized by a positive integer $k\ge 2$. We show that under uniform traffic, our policy achieves an expected total queue length of $O\bigl({n\log\max\{n,1/(1-ρ)\}}\big/{(1-ρ)^{2^k/(2^k-1)}}\bigr)$, as long as $ρ\to 1$ in the large-system regime. As $k$ increases, the exponent $2^k/(2^k-1)$ approaches $1$, bringing our bound arbitrarily close to the conjectured scaling. The expected amortized scheduling cost of the policy is $O(n^3 k)$ per time slot. Our policy is of a batching type, with a novel recursive design that allows an arbitrary number of batching levels. This design principle may also be useful for other scheduling problems in which combinatorial constraints restrict which jobs can be served simultaneously.

0.20

Metric Facility Location under Batched Random Order

cs.DS ·2026-11-03 ·Fabrizio Grandoni, Stefano Leonardi, Matteo Russo
theory similarity 0.58
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

Tight asymptotic competitive ratio for the Canadian Traveller Problem on unit-weighted grids

cs.DS ·2026-10-09 ·Pierre Bergé, Vsevolod Chernyshev, Malory Marin, Alexey Pyrko, Lou Salaün
theory similarity 0.57
Abstract

We study the $k$-Canadian Traveller Problem (k-ctp), an online navigation problem introduced by Papadimitriou and Yannakakis in 1991. Given an undirected weighted graph $G=(V,E,ω)$ and two vertices $s,t\in V$, a traveller aims at navigating from $s$ to $t$ while minimizing the total distance travelled. However, up to $k$ edges of the graph may be blocked, and the traveller discovers that an edge is blocked only upon reaching one of its endpoints. The performance of an online algorithm for k-ctp is measured with the competitive ratio, which is the quotient between the distance actually traversed and the distance traversed by an omniscient traveller who knows all blockages in advance. A general lower bound $2k+1$ for the competitive ratio of deterministic algorithms remains valid even when the input graph is series-parallel, whereas constant competitive ratios can be achieved on restricted graph classes, such as cycles or unit-weighted outerplanar graphs. In this paper, we establish the first intermediate competitive ratio between constant and linear regimes. We prove that, on unit-weighted solid grid graphs, there exists an online algorithm with competitive ratio $O(\sqrt{k})$. This ratio is asymptotically tight and cannot be defeated, even on unit-weighted square grids. Finally, we show that both the unit-weighted and solidity assumptions are essential: going further with arbitrary edge weights (even on square grids) or non-solid unit-weighted grid structures yields a linear lower bound of $Ω(k)$.

0.25

How Much Can Approximate Equilibria Change the Social Cost of Selfish Routing?

cs.GT cs.AIcs.DSmath.OC ·2026-10-31 ·Yu Cheng, Tianle Jiang
similarity 0.57
Abstract

We study approximate Nash equilibria in nonatomic congestion games, with the goal of understanding how much the social cost can change when the equilibrium condition is relaxed. We consider $ε$-approximate Nash equilibria ($ε$-NE), in which each player uses a strategy whose cost is at most $1 + ε$ times the minimum available cost. We compare the social costs of $ε$-NE and exact Nash equilibria. This lets us quantify, for example, how much a navigation app can reduce total travel time when drivers tolerate routes slightly slower than the fastest available route. For degree-$d$ polynomial latencies in both general nonatomic congestion games and single-commodity routing games on series-parallel networks, we give tight lower and upper bounds on the relative change in social cost from an exact Nash equilibrium to any $ε$-NE, with matching instances for every $ε$. For small $ε$, the largest possible relative reduction and increase in general congestion games are both $Θ(\sqrt{dε})$, independently of the number of resources and populations. In contrast, on series-parallel networks of depth $h$, the largest possible relative reduction is $Θ(hε)$, while the largest possible relative increase is known to be $ε$. For the classes of games we study, these results give a tight and quantitative characterization of the possible changes in social cost and establish a separation between general and series-parallel networks.

0.13