Skip to content

Online Covering with Maximum Delay under Subadditive Service Costs

Sep 2026 · arXiv.org · Vol abs/2609.32675 · 1 citation · 11 references
Computer Science

TL;DR

Online covering in which each instantaneous service pays its purchase cost and one maximum waiting time, with no effect on future requests is studied, finding an offline consecutive-batch normal form that transfers static approximation guarantees to the offline problem.

Abstract

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 $\rho$ yields ratios $\rho+1$ deterministically and $1/(1-e^{-1/\rho})$ 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.

View source

Similar papers

Preprint Aug 2026

Online Bin Packing with Per-Bin Maximum Delay

This work proves strong NP-hardness and rule out absolute approximation factors below three halves unless P equals NP, and obtains an exact stochastic benchmark for Poisson arrivals when every item has half the bin capacity.

Tian-Han Lu, Run-Tian Ren, Sheng-Cai Liu · 0 citations
Preprint Sep 2026

Degree-Parameterized Analysis of Sampling-Based Online Matching

We study edge-weighted online bipartite matching under random arrival order, parameterized by the maximum offline degree $d$ and sampling fraction $\theta$. We analyze two sampling-based frameworks. For \emph{Deterministic Greedy Sampling}, which computes prices from a fixed-size initial sample and then applies a local...

Pan Xu · 0 citations
Preprint Oct 2026

Optimal Online Stochastic Matching

We resolve the problem of unweighted online stochastic matching with a known arrival law by establishing its optimal competitive ratio. For Poisson arrivals, we achieve $1-e/e^e\approx0.8206$, matching the upper bound of Chierichetti, Giacchini, Panconesi, and Vattani [ICALP 2025]. For exactly $n$ i.i.d.~arrivals, we o...

Paul Duetting, Michal Feldman, Mathieu Molina · 0 citations
Preprint Oct 2026

Efficient Algorithms for Online Subadditive Combinatorial Allocations

For the online combinatorial allocation problem with subadditive valuations, Correa and Cristi (STOC 2023) proved the existence of a $6$-competitive online algorithm, improving on the previous best $O(\log\!\log m)$-competitive online algorithm due to D\"utting, Kesselheim, and Lucier (FOCS 2020), where $m$ is the numb...

Calum MacRury, Rian Neogi, Kanstantsin Pashkovich et al. · 1 citation
Preprint Sep 2026

Online Matching in Convex Bipartite Graphs

Online resource-allocation systems, like outpatient scheduling and spectrum allocation, often assign sequentially arriving requests to an ordered pool of scarce resources, where each request accepts a contiguous interval of feasible options. We study the resulting online matching problem on convex bipartite graphs unde...

Yi-Long Feng, Zhihao Gavin Tang, Kang-Ning Wang et al. · 0 citations
Preprint Sep 2026

A PTAS for Non-Adaptive Stochastic Top-$k$ Sum under General Combinatorial Constraints

We study non-adaptive selection of a feasible set $S$ that maximizes the expected sum of the $k$ largest realized values among independent nonnegative discrete random variables. The same objective arises in team hiring and as VCG welfare in an $\ell$-unit auction. The main setting is a fixed-dimensional nonnegative pac...

Yu Liu · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.