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 com...
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...
The deterministic guarantee matches the known fixed-node lower bound, and the matching randomized lower bound are proved, ensuring that both guarantees are optimal on every nondegenerate rooted tree.
Tian-Han Lu, Run-Tian Ren, Sheng-Cai Liu et al.· 3 citations
We study online service with one maximum-waiting-time charge per service batch. The persistent server endpoint prevents a phase-by-phase comparison with the offline optimum: an offline schedule may merge many online phases, share movement globally, and finish at unrelated endpoints. Our main contribution is a metric-in...
Tian-Han Lu, Run-Tian Ren, Sheng-Cai Liu et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
