Abstract. We present a 1 − 1 √ k -competitive algorithm for the online stochastic generalized assignment problem under the assumption that no item takes up more than 1 k fraction of the capacity of any bin. Items arrive online; each item has a value and a size; upon arrival, an item can be placed in a bin or discarded; the objective is to maximize the total value of the placement. Both value and size of an item may depend on the bin in which the item is placed; the size of an item is revealed only after it has been placed in a bin; distribution information is available about the value and size of each item in advance (not necessarily i.i.d), however items arrive in adversarial order (non-adaptive adversary). We also present an application of our result to subscription-based advertising where each advertiser, if served, requires a given minimum number of impressions (i.e., the "all or nothing" model).
-competitive algorithm in expectation for the online GAP REF , where similar to prior work two restrictions are made; that the weights and sizes of each item are stochastic and each items' size is less than a 1 k of the bin capacity.
The Online Stochastic Generalized Assignment Problem
APPROX-RANDOM
Computer Science