The search functionality is under construction.

Author Search Result

[Author] Kanaho HANJI(1hit)

1-1hit
  • Online Removable Knapsack Problem for Integer-Sized Unweighted Items Open Access

    Hiroshi FUJIWARA  Kanaho HANJI  Hiroaki YAMAMOTO  

     
    PAPER-Algorithms and Data Structures

      Pubricized:
    2022/03/08
      Vol:
    E105-A No:9
      Page(s):
    1195-1202

    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.