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.
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.
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.
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
This paper presents significant upper-bound improvements for dynamic 2D square bin packing, where square items arrive and depart over time and the objective is to minimize the peak number of concurrent active unit bins. In our model, repacking is permitted only within a destination bin upon item arrival; migration betw...
Miguel A. Mini, F. Miyazawa, Gabriela M. Silva et al.· 0 citations
A new randomized online algorithm for additive and submodular valuations, called Single-or-Sample, is developed, that achieves a constant-factor approximation to MMS simultaneously for all agents, with constant probability, and establishes a fundamental tradeoff between approximation and success probability.
Shuchi Chawla, Zhi-Yi Huang, Pooja Kulkarni et al.· 1 citation
This work uses spatial blindness---announced requests whose locations are revealed only when visited---as a stress test: dyadic exploration preserves a constant ratio on a known finite line, while a single hidden request on a star forces a loss linear in its degree.
Tian-Han Lu, Run-Tian Ren, Sheng-Cai Liu et al.· 0 citations
We study online allocation with increasing returns, where an uncertain number of customers arrive sequentially and can be irrevocably assigned to any product with remaining capacity. Each assignment earns a base reward plus a bonus that is nondecreasing in the number of previous assignments to the same product. Prior w...
Shuo Sun, Yun-Duan Lin· arXiv.org· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.