CS Paper Radar

Fundamental Limits of Covert queueing under Busy-Period Observations

Anumula Venkata Sai Sree Sahithi, Arti Yardi, Jithin Ravi

cs.IT math.PR ·submitted 2026-10-09 17:50 UTC · v1

Abstract

Consider a queueing system operated by Bob, which is intended to serve only jobs generated by a legitimate user, Willie. Willie's jobs arrive according to a Poisson process, and the service times are exponentially distributed. Bob seeks to covertly serve additional jobs arriving according to an independent Poisson process, without Willie detecting their presence. As the legitimate user, Willie is provided with certain statistics of each busy period by Bob. In particular, we consider two statistics: (i) the number of jobs served during each busy period and (ii) the duration of each busy period. We establish that, under either statistic, the maximum expected number of additional jobs that Bob can covertly serve obeys a square-root law. Specifically, over n busy periods, Bob can covertly serve additional jobs in the order of square root of n, whereas any scaling which is above square root of n enables Willie to asymptotically detect the presence of these additional jobs with vanishing error probability. Furthermore, we characterize the scaling constant associated with the square-root law, which we refer to as the covert queueing constant, for each of the two statistics. We compare the scaling constants corresponding to the two statistics and argue that the scaling constant under statistic (i) is no greater than that under statistic (ii).

Comment
13 pages, 2 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Tandem Queues with Hybrid Abandonment in Heavy Traffic

cs.PF math.PR ·2026-10-08 ·Cameron Curtis, Izzy Grosof, Seyed Iravani
theory similarity 0.62
Abstract

Hybrid-abandonment systems, where jobs abandon from certain stages of service but not others, occur frequently in medical, service, and computing systems. Abandonment affects the heavy-traffic behavior of both the stages with and without abandonment. In contrast to existing heavy-traffic works that focus on cases where there is abandonment at either all stages or no stages, we focus on the heavy-traffic behavior for these hybrid-abandonment systems. We provide the first heavy-traffic characterization of the second queue length in a two-stage tandem queue with abandonment only in the first stage. We characterize the scaled mean of the second stage queue length and prove that the scaled second queue length is asymptotically exponentially distributed and asymptotically independent of the first stage queue length. We derive our results by analyzing Markovian arrival process queues with countably infinite phases. We do this by extending techniques used to analyze queues with Markov-modulated arrivals to the broader class of infinite Markovian arrival process queues. We prove asymptotic results for a more general infinite phase process condition, an infinite birth-death phase process, and the hybrid-abandonment tandem case. We also empirically demonstrate that our heavy-traffic approximations are good approximations across various system settings.

0.25

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

cs.PF math.PR ·2026-10-27 ·Taha Ameen, Weina Wang
similarity 0.62
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

Sharp Bounds for Truthful-in-Expectation Scheduling

cs.GT ·2026-11-03 ·Yunpeng Li
theory similarity 0.61
Abstract

We study randomized mechanisms for scheduling indivisible jobs on $n$ unrelated machines. Each machine is controlled by a selfish agent who privately knows its processing time for each job. A mechanism assigns every job to a machine and makes payments. We require truthfulness in expectation: no agent can increase its expected payment minus its expected processing cost by misreporting, regardless of the other agents' reports. The makespan is the maximum total processing time assigned to a machine; the objective is to minimize its expectation. We prove that the optimal approximation ratio is $(n+1)/2$ for every $n\ge7$, relative to the minimum makespan of an integral assignment. The lower bound holds for every $n$ and allows unrestricted computation and arbitrary correlations among assignments, assuming finite expected payments and a guarantee uniform over all finite job counts. The matching mechanism uses correlated rounding and runs in expected polynomial bit time on rational inputs. These guarantees hold for all finite nonnegative processing times. For two machines, we characterize the optimal approximation ratio exactly as an analytic constant, approximately $1.505995705434$, and give a mechanism attaining it. For three machines the optimal ratio is $2$. For four, five, and six machines we obtain upper bounds of $3$, $105/32$, and $29/8$, respectively, compared with the general lower bound $(n+1)/2$. The proofs for $n\ge7$ do not rely on computer-assisted certificates; the two- and three-machine results use exact rational computer-assisted certificates.

0.18

Randomized Algorithm for MMS Allocation of Chores with Online Agent Arrivals

cs.GT ·2026-10-11 ·Haolong Li, Fangxiao Wang, Xiaowei Wu
similarity 0.60
Abstract

We study the fair allocation of $m$ indivisible chores among $n$ agents in the agent-arrival model against an oblivious adversary. The chore set and the number of agents are known in advance. When agent $i$ arrives, her nonnegative additive cost function $c_i$ is revealed, and the algorithm must immediately and irrevocably assign her a subset of the unallocated chores. We focus on the notion of maximin share (MMS) and measure the fairness of the realized allocation $X$ by the ex-post MMS approximation ratio $ρ(X)$. We measure an algorithm's performance by its expected ratio, and also the guarantees that hold with high probability. For binary additive costs, we achieve an expected ex-post MMS ratio of $3/2+o(1)$, and show that every randomized online algorithm has an expected ratio of at least $3/2-o(1)$. For every $n$, the expected ratio is at most $1.755$. A variant of our algorithm guarantees an approximation ratio of $2$ with high probability, which is optimal. % For general additive costs, we present a weighted-rounding algorithm that achieves an expected ratio of $2+o(1)$, which also holds with high probability. The expected ratio is at most $2.594$ for every $n$. We also show that similar algorithms extend to additive goods, achieving a constant expected ex-post MMS ratio and guaranteeing every agent an $x$-fraction of her MMS with probability at least $1-85x^2$ for every $x\le1/15$.

0.39

Online Bin Packing with Per-Bin Maximum Delay

cs.DS ·2026-08-27 ·Tianhang Lu, Runtian Ren, Shengcai Liu
benchmarktheory similarity 0.59
Abstract

We study online bin packing with per-bin maximum delay: each sealed bin incurs a unit opening cost plus the longest waiting time among its items. Offline, this becomes a temporal-span packing objective. We prove strong NP-hardness and rule out absolute approximation factors below three halves unless P equals NP. We complement these barriers with a polynomial constant-factor approximation, exact algorithms for several special cases, and an AFPTAS for the fixed-length weighted endpoint subproblem. For adversarial online inputs, we give an efficient randomized algorithm in the ideal random-real model with expected competitive ratio about 2.418 against an oblivious adversary, together with deterministic and randomized lower bounds. Its analysis couples Next-Fit fragmentation to a negative credit generated by silence clusters. Both frontiers are solved exactly when capacity is nonbinding. We also obtain an exact stochastic benchmark for Poisson arrivals when every item has half the bin capacity: we characterize the offline rate, identify an optimal causal policy, and show that two natural asymptotic ratio notions agree and are bounded by four thirds.

0.08

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

A Parameter-Free Best-of-Both-Worlds Policy for Queueing Bandits

cs.LG ·2026-11-02 ·Jongyeong Lee, Chansoo Kim
theory similarity 0.57
Abstract · Preprint

We study online channel scheduling for a single queue served by $K$ channels under bandit feedback. We propose a simple best-of-both-worlds policy that explores when the queue is empty. During busy periods, it selects the empirical best channel while the prescribed conditions hold and, if any condition is violated, switches to a robust bandit policy to clear the queue. For arbitrary arrivals and services determined by an oblivious adversary, our policy achieves $\tilde{\mathcal{O}}(\sqrt{K L_T})$ worst-case queue length regret with high probability, where $L_T$ is the longest busy-period length. This result improves the previous $T^{3/4}$ dependence and matches the worst-case lower bound up to logarithmic factors. Under bounded i.i.d. stochastic models with a unique best stabilizing channel, we show that the cumulative queue length regret converges to a finite problem-dependent constant, and further establish the logarithmic expected worst-case queue length regret bound.

0.19

Learning While Scheduling Jobs under Context-Dependent Service Rates: An Anytime Rate-Optimal Algorithm

cs.LG ·2026-10-05 ·Seoungbin Bae, Dabeen Lee
theory similarity 0.57
Abstract

We study contextual queueing bandits, where a learner schedules jobs while learning unknown service rates modeled by logistic functions of job-server features. Performance is measured by queue length regret, the expected excess queue length at round $t$ relative to an oracle that knows the service rates. Existing decaying-regret guarantees either have a suboptimal decay rate or require a known fixed horizon. They also assume context-wise slack and a strictly positive minimum eigenvalue of the feature covariance. In this paper, we propose WISE (Widest Interval Selection with Elimination), achieving rate-optimal $\widetilde{\mathcal O}(t^{-1/2})$ queue length regret at every sufficiently large time without knowing the horizon. We assume capacity slack, meaning that expected incoming workload under best-server service is below service capacity, and impose no covariance lower bound. Our analysis uses a workload potential measuring the expected service attempts needed by waiting jobs on their best servers. Its drift on nonempty rounds combines a negative term ensured by capacity slack with errors from suboptimal service choices. Then an elliptical potential count bounds how often WISE selects wide confidence intervals, thereby limiting the number of rounds with large service errors. We also sharpen the arrival-rate dependence of an existing lower bound and make its dependence on feature dimension and server count explicit. We prove another lower bound that quantifies the increase in regret as the normalized capacity slack decreases; to our knowledge, this is the first such lower bound for CQB. Simulations show small regret even when context-wise slack fails.

0.20