Removable Online Knapsack with Bounded Size Items
Pages 283 - 296
Abstract
In the online unweighted knapsack problem, some items arrive in sequence and one has to decide to pack them or not into a knapsack of given capacity. The objective is to maximize the total size of packed items. In the traditional setting, decisions are irrevocable, and the problem cannot admit any -competitive algorithm. The removable nature of the items allows to withdraw previously packed elements of the current solution. This feature makes the online knapsack problem amenable to competitive analysis under the ratio of , which is at the same time the best possible performance guarantee [12]. This article deals with refinements of the best possible competitive ratio of the online unweighted knapsack problem with removable items when either an upper or a lower bound on the size of the items is known.
References
[1]
Albers S Online algorithms: a survey Math. Program. 2003 97 1–2 3-26
[2]
Babaioff, M., Hartline, J.D., Kleinberg, R.D.: Selling ad campaigns: online algorithms with cancellations. In: Chuang, J., Fortnow, L., Pu, P. (eds.) Proceedings 10th ACM Conference on Electronic Commerce (EC-2009), Stanford, California, USA, 6–10 July 2009, pp. 61–70. ACM (2009)
[3]
Böckenhauer, H., Burjons, E., Hromkovic, J., Lotze, H., Rossmanith, P.: Online simple knapsack with reservation costs. In: Bläser, M., Monmege, B. (eds.) STACS 2021, 16–19 March 2021, Saarbrücken, Germany (Virtual Conference). LIPIcs, vol. 187, pp. 16:1–16:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
[4]
Böckenhauer H, Komm D, Královic R, and Rossmanith P The online knapsack problem: advice and randomization Theor. Comput. Sci. 2014 527 61-72
[5]
Cygan M, Jez L, and Sgall J Online knapsack revisited Theory Comput. Syst. 2016 58 1 153-190
[6]
Demko S and Hill TP Equitable distribution of indivisible objects Math. Soc. Sci. 1988 16 2 145-158
[7]
Han X, Kawase Y, and Makino K Online unweighted knapsack problem with removal cost Algorithmica 2014 70 1 76-91
[8]
Han X, Kawase Y, and Makino K Randomized algorithms for online knapsack problems Theor. Comput. Sci. 2015 562 395-405
[9]
Han X, Kawase Y, Makino K, and Guo H Online removable knapsack problem under convex function Theor. Comput. Sci. 2014 540 62-69
[10]
Han, X., Kawase, Y., Makino, K., Yokomaku, H.: Online knapsack problems with a resource buffer. In: Lu, P., Zhang, G. (eds.) ISAAC 2019, 8–11 December 2019, Shanghai University of Finance and Economics, Shanghai, China. LIPIcs, vol. 149, pp. 28:1–28:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
[11]
Han X and Makino K Online removable knapsack with limited cuts Theor. Comput. Sci. 2010 411 44–46 3956-3964
[12]
Iwama, K., Taketomi, S.: Removable online knapsack problems. In: ICALP 2002, Malaga, Spain, 8–13 July 2002, Proceedings, pp. 293–305 (2002)
[13]
Iwama K and Zhang G Online knapsack with resource augmentation Inf. Process. Lett. 2010 110 22 1016-1020
[14]
Kellerer H, Pferschy U, and Pisinger D Knapsack Problems 2004 Berlin Springer
[15]
Lueker GS Average-case analysis of off-line and on-line knapsack problems J. Algorithms 1998 29 2 277-305
[16]
Marchetti-Spaccamela A and Vercellis C Stochastic on-line knapsack problems Math. Program. 1995 68 73-104
[17]
Zhou Y, Chakrabarty D, and Lukose R Papadimitriou C and Zhang S Budget constrained bidding in keyword auctions and online knapsack problems Internet and Network Economics 2008 Heidelberg Springer 566-576
Recommendations
Dynamic bin packing of unit fractions items
This paper studies the dynamic bin packing problem, in which items arrive and depart at arbitrary times. We want to pack a sequence of unit fractions items (i.e., items with sizes 1/w for some integer w>=1) into unit-size bins, such that the maximum ...
Online Knapsack Revisited
We investigate the online variant of the (Multiple) Knapsack Problem: an algorithm is to pack items, of arbitrary sizes and profits, in k knapsacks (bins) without exceeding the capacity of any bin. We study two objective functions: the sum and the ...
Online Results for Black and White Bin Packing
In online bin packing problems, items of sizes in [0, 1] are to be partitioned into subsets of total size at most 1, called bins. We introduce a new variant where items are of two types, called black and white, and the item types must alternate in each ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Feb 2024
513 pages
ISBN:978-3-031-52112-6
DOI:10.1007/978-3-031-52113-3
- Editors:
- Henning Fernau,
- Serge Gaspers,
- Ralf Klasing
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 19 February 2024
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 02 Oct 2024
Other Metrics
Citations
View Options
View options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in