The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
조회수
135
온라인 이동식 배낭 문제에서는 각각의 가치와 크기가 표시된 일련의 항목이 하나씩 주어집니다. 아이템이 도착할 때마다 플레이어는 해당 아이템을 배낭에 넣을지 아니면 버릴지를 결정해야 합니다. 플레이어는 이미 배낭에 들어 있는 일부 항목을 버릴 수도 있습니다. 목표는 배낭의 총 가치를 극대화하는 것입니다. Iwama와 Taketomi는 각 항목의 값이 해당 크기와 같은 경우에 대한 최적의 알고리즘을 제공했습니다. 본 논문에서는 배낭의 용량이 양의 정수라는 추가적인 제약 조건이 있는 경우를 고려합니다. N 항목의 크기는 모두 필수입니다. 각 양의 정수에 대해 N, 우리는 알고리즘을 설계하고 최적성을 증명합니다. 경쟁률은 단조롭지 않은 것으로 나타났습니다. N.
Hiroshi FUJIWARA
Shinshu University
Kanaho HANJI
Shinshu University
Hiroaki YAMAMOTO
Shinshu University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
부
Hiroshi FUJIWARA, Kanaho HANJI, Hiroaki YAMAMOTO, "Online Removable Knapsack Problem for Integer-Sized Unweighted Items" in IEICE TRANSACTIONS on Fundamentals,
vol. E105-A, no. 9, pp. 1195-1202, September 2022, doi: 10.1587/transfun.2021DMP0013.
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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2021DMP0013/_p
부
@ARTICLE{e105-a_9_1195,
author={Hiroshi FUJIWARA, Kanaho HANJI, Hiroaki YAMAMOTO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Online Removable Knapsack Problem for Integer-Sized Unweighted Items},
year={2022},
volume={E105-A},
number={9},
pages={1195-1202},
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.},
keywords={},
doi={10.1587/transfun.2021DMP0013},
ISSN={1745-1337},
month={September},}
부
TY - JOUR
TI - Online Removable Knapsack Problem for Integer-Sized Unweighted Items
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1195
EP - 1202
AU - Hiroshi FUJIWARA
AU - Kanaho HANJI
AU - Hiroaki YAMAMOTO
PY - 2022
DO - 10.1587/transfun.2021DMP0013
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E105-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2022
AB - 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.
ER -