IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Online ISSN : 1745-1337
Print ISSN : 0916-8508

This article has now been updated. Please use the final version.

Online Removable Knapsack Problem for Integer-Sized Unweighted Items
Hiroshi FUJIWARAKanaho HANJIHiroaki YAMAMOTO
Author information
JOURNAL FREE ACCESS Advance online publication

Article ID: 2021DMP0013

Details
Abstract

In the online removable knapsack problem, a sequence of items, each labeled with its value and its size, is given one by one. At each arrival of an item, a player has to decide whether to put it into a knapsack or to discard it. The player is also allowed to discard some of the items that are already in the knapsack. The objective is to maximize the total value of the knapsack. Iwama and Taketomi gave an optimal algorithm for the case where the value of each item is equal to its size. In this paper we consider a case with an additional constraint that the capacity of the knapsack is a positive integer N and that the sizes of items are all integral. For each positive integer N, we design an algorithm and prove its optimality. It is revealed that the competitive ratio is not monotonic with respect to N.

Content from these authors
© 2022 The Institute of Electronics, Information and Communication Engineers
feedback
Top