CS Paper Radar

Capacitated Line Aggregation with Maximum Delay

Runtian Ren, Shengcai Liu

cs.DS ·submitted 2026-10-19 14:34 UTC · v1

Abstract

We study capacitated line aggregation with per-batch maximum delay. Requests arrive over time at locations on a rooted half-line and are served in instantaneous batches of at most $k$ requests. Each batch pays the distance to its farthest request plus the waiting time of its oldest request. The objective is to minimize the total cost. We give a deterministic online algorithm with competitive ratio $36+12\sqrt3$. The algorithm uses a Next Fit idea along paths of nested time intervals: it assigns a new group to an existing batch when a path-load test permits, and opens a new batch otherwise. The path load controls both capacity and the cost of opening new batches. Randomizing the common scale improves the expected competitive ratio to $(18+6\sqrt3)/\ln2$ against an oblivious adversary. Both guarantees extend to arbitrary indivisible request sizes. We also study capacitated LAD in the learning-augmented model. Advice revealed at its service times allows $(1+ε)$-consistency against every complete feasible advice schedule and $O(ε^{-2})$-robustness. The analysis charges repeated switches to successive decreases in the remaining advice cost.

Closest papers

Nearest neighbours by meaning across the whole index.

Online Line Aggregation with Deadlines: Randomized Guarantees and Learning-Augmented Tradeoffs

cs.DS math.OC ·2026-08-13 ·Tianhang Lu
theory similarity 0.73
Abstract

We study online line aggregation with deadlines, where requests arrive over time on the positive half-line and a service at location $y$ clears all pending requests in $[0,y]$ at cost $y$. In the classical adversarial setting, we propose an $e$-competitive randomized algorithm against an oblivious adversary and prove a matching lower bound. Thus $e$ is the optimal randomized competitive ratio. We then consider advice in the form of an offline feasible solution. For every confidence parameter $λ\in(0,1]$, our deterministic learning-augmented algorithm is $(1+3/λ)$-robust and $(1+3λ)$-consistent. We also propose a randomized learning-augmented algorithm that is $(e+e/λ)$-robust and $(e-1+λ)$-consistent against an oblivious adversary. For the offline problem, we present a polynomial-time dynamic programming algorithm. Numerical experiments complement the worst-case analysis: accurate advice lowers service costs, while both learning-augmented algorithms remain stable as the advice becomes increasingly noisy.

0.04

Online Service with Per-Batch Maximum Delays

cs.DS ·2026-08-19 ·Tianhang Lu, Runtian Ren, Shengcai Liu, Ke Tang
similarity 0.71
Abstract

We study online service with per-batch maximum delays on a finite metric space. Requests arrive over time, and a server serves each batch by following a walk visiting its requests' locations. Movement is instantaneous. The objective is to minimize the total distance traveled by the server plus the sum, over all batches, of the maximum waiting time in each batch. We give deterministic polynomial-time algorithms with competitive ratios $10$ on finite lines, $12$ on weighted trees, and $20$ on arbitrary finite metrics. Unlike additive delay, maximum delay allows younger requests to join a batch without increasing its delay charge. Our algorithms coordinate service using a common waiting clock and a threshold determined by the metric. The analysis uses certificates for groups of requests to compare this policy with any offline schedule, even one that serves different batches and follows different walks. This comparison shows that coordinating service in this way loses only a constant factor. The bounds hold whether the server must serve requests it visits or may leave them unserved; the two rules also have equal offline optimal costs. Offline optimization is polynomial on lines and explicitly represented weighted trees, and NP hard on general metrics. When arrivals are announced but locations are hidden until visited, we give an $84$-competitive algorithm on a known finite line under either rule.

0.13

Online Network Design with Maximum Delay and Stochastic Arrivals

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

Stochastic Aggregation with Prescribed Resources and Additive Delay

cs.DS ·2026-11-10 ·Tianhang Lu, Runtian Ren, Shengcai Liu
similarity 0.70
Abstract

We study online aggregation with prescribed resources and additive delay. In this problem, we are given a finite set of resources with purchase costs and a collection of request types, each specifying the resources it requires. Requests arrive over time, and each request can be served immediately or postponed to a later time. A service may serve several pending requests together by purchasing every resource required by at least one of them, paying for each purchased resource only once. These purchases serve only the current batch; resources needed in a later service must be purchased again. A request served $t$ units of time after its arrival incurs delay cost $t$. The objective is to serve all requests while minimizing the sum of resource purchase costs and individual delay costs. We consider a stochastic version of this problem in which requests of each type follow an independent Poisson process of known rate. An online algorithm knows these rates but observes requests only upon arrival. We compare its expected cost with that of an offline optimum that knows the entire realized input and may choose every batch freely. A resource--scale linear program supplies both an offline lower certificate and synchronized service periods. This yields a deterministic online algorithm with polynomial-time preprocessing on rational input and a long-run ratio of expectations below $2.113$. The guarantee applies in particular to rooted multi-level aggregation and prescribed-pair aggregation on trees. Besides, for Poisson TCP acknowledgment, we further characterize the optimal long-run ratio of expectations at every load, showing that its worst-case value is approximately 1.409 and is attained by a deterministic online policy.

0.18

List Update with Time Windows and Delays without Batch-Serving

cs.DS ·2026-11-12 ·Icey Siyi Ai, Jingwei Li, Clifford Stein
theory similarity 0.69
Abstract

We study list update with time windows and delays when every request requires a separate access. Unlike batch-serving models, serving several requests to one element still incurs one access per request, and each access may change the list for subsequent requests. For time windows of overlap at most $k\ge2$, our deterministic First-Element Removal algorithm is $(3-2/k)$-competitive, hence $3$-competitive in general. Against an oblivious adversary, a randomized adaptation of BIT is $7/4$-competitive on arbitrary $2$-overlap inputs. More generally, on inputs without self-overlap, it is $\left(13/4-9/[2(k+1)]\right)$-competitive for every $k\ge2$. For delays, we give a deterministic $5$-competitive algorithm and a lower bound of $2+\sqrt3$ for deterministic delay-unaware algorithms. Our analyses extend inversion potentials with per-request credits that reconcile different service times and orders.

0.21

Online Covering with Maximum Delay under Subadditive Service Costs

cs.DS ·2026-09-26 ·Tianhang Lu, Runtian Ren, Shengcai Liu
theory similarity 0.69
Abstract · 23 pages, 4 figures

We study online covering in which each instantaneous service pays its purchase cost and one maximum waiting time, with no effect on future requests. For static realizable services, monotone subadditivity suffices for optimal competitive ratios; submodularity is unnecessary. A normalized monotone subadditive lower-bound oracle with realization factor $ρ$ yields ratios $ρ+1$ deterministically and $1/(1-e^{-1/ρ})$ randomly against an oblivious adversary. Exact batch optimization gives the optimal constants $2$ and $e/(e-1)$. The randomized algorithm uses one global threshold on a seed-independent virtual-height trajectory, whose active time is a lower bound on the offline optimum. Weighted vertex cover gives a strict separation from submodularity on a three-edge bipartite path, with polynomial-time batch implementations through min-cut and LP rounding. An offline consecutive-batch normal form also transfers static approximation guarantees to the offline problem.

0.09

Online Batching with Lookahead: Adversarial Limits and Stochastic Gains

cs.DS ·2026-10-12 ·Dimitris Christou, Jiayi Chen, Nihal Sharma, Aditya Akella, Shuchi Chawla +1 more
benchmarktheoryhot direction similarity 0.66
Abstract

Modern inference systems rely on batching to exploit parallel execution and amortize serial execution overheads, but batching creates a fundamental online scheduling tradeoff: serving requests immediately reduces request queuing delay, while waiting can form larger batches that better utilize parallel hardware and improve serving efficiency. We study this tradeoff in a single-server online batching model with bounded batch capacity, fixed batch processing time, and the objective of minimizing total flow time. Our focus is on the value of finite lookahead into future arrivals over a purely online setting for scheduling. We show that the benefits of lookahead depend on the arrival model. In the adversarial setting, finite perfect lookahead has inherent limitations: for any bounded lookahead window, every online algorithm remains separated from the offline optimum by a constant factor. Thus, worst-case arrival sequences can prevent perfect knowledge of future events from fully overcoming online uncertainty. In contrast, under Poisson arrivals in the stable regime, finite lookahead is much more powerful. Although the best distribution-aware online algorithm has a nonzero asymptotic gap from the offline optimum, lookahead closes this gap exponentially fast in the window length. We prove matching upper and lower bounds up to constants in the exponent. Together, these results give a tight characterization of when lookahead can close the online--offline gap, incorporating insights from the competitive analysis of online algorithms into queueing-theoretic steady-state bounds. We also study imperfect predictions, showing that the benefit of lookahead degrades gracefully with prediction error. Simulations on synthetic arrivals and experiments on real request traces support the theory: modest lookahead substantially reduces flow time and brings online batching close to the offline benchmark.

0.55

Spot Markets for AI Inference: Dynamic Capacity Allocation and Pricing on a Shared Accelerator Fleet

eess.SY ·2026-11-08 ·Quanyan Zhu
similarity 0.66
Abstract · 39 pages, 12 figures, 4 tables

Inference providers size their accelerator fleets for the interactive peak and sell spare capacity through fixed discounts, such as batch tiers at half price. However, inference differs from conventional cloud capacity in four respects: capacity depends on the latency tier through batching, moving weights between models is slow and costly, spot demand can wait until its deadline, and power can bind. In this paper, we develop a framework for dynamic capacity allocation and pricing of AI inference on a shared accelerator fleet. We consider a provider that serves several models under a power cap and sells each model in an interactive tier with a speed promise and in a spot tier for preemptible work with a deadline. In each period, the provider chooses how many replicas of each model to keep loaded and what spot price to quote. We show that one interactive token displaces a fixed number $ρ_m>1$ of spot tokens, and that the optimal spot price lies midway between the interactive price and the effective cost of capacity in the deadline window, which is close to the prevailing half price only when the fleet is slack. We further show that a spot tier raises the optimal reliability of the interactive tier, and that placement should follow persistent demand shifts while prices absorb transients. Building on these results, we design a model predictive controller based on a linear program with explicit approximation bounds, which solves each period in milliseconds. Numerical experiments on a simulated week with a measured daily demand profile, a flash crowd, and a grid curtailment show that the controller raises profit by 7.4% over fixed half-price practice, captures 93% of the gain available with perfect forecasts, keeps the interactive promise through both events, and leaves spot buyers better off.

0.28