查看文章

The online knapsack problem (OKP) is a generalized version of the 0-1 knapsack problem (0-1KP) to a setting in which the problem inputs are revealed over time. Whereas the 0-1KP involves the maximization of the value of the knapsack contents without exceeding its capacity, the OKP involves the following additional requirements: items are presented one at a time, their features are only revealed at their arrival, and an immediate and irrevocable decision on the current item is required before observing the next one. This problem is known to be non-approximable in its general case. Accordingly, we study a relaxed variant of the OKP in which items delay is allowed: we assume that the decision maker is allowed to retain the observed items until a given deadline before deciding definitively on them. The main objective in this problem is to load the best subset of items that maximizes the expected value of …