Abstract
In this paper, we address the online minimization knapsack problem, i. e., the items are given one by one over time and the goal is to minimize the total cost of items that covers a knapsack. We study the removable model, where it is allowed to remove old items from the knapsack in order to accept a new item. We obtain the following results.
-
1
We propose an 8-competitive deterministic and memoryless algorithm for the problem, which contrasts to the result for the online maximization knapsack problem that no online algorithm has a bounded competitive ratio [8].
-
2
We propose a 2e-competitive randomized algorithm for the problem.
-
3
We derive a lower bound 2 for deterministic algorithms for the problem.
-
4
We propose a 1.618-competitive deterministic algorithm for the case in which each item has its size equal to its cost, and show that this is best possible.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Babat, L.G.: Linear functions on the N-dimensional unit cube. Dokl. AKad. Nauk SSSR 222, 761–762 (1975) (Russian)
Csirik, J., Frenk, J.B.G., Labbé, M., Zhang, S.: Heuristics for the 0-1 Min-Knapsack problem. Acta Cybernetica 10(1-2), 15–20 (1991)
Güntzer, M.M., Jungnickel, D.: Approximate minimization algorithms for the 0/1 knapsack and subset-sum problem. Operations Research Letters 26, 55–66 (2000)
Gene, G., Levner, E.: Complexity of approximation algorithms for combinatorial problems: a survey. ACM SIGACT News 12(3), 52–65 (1980)
Horiyama, T., Iwama, K., Kawahara, J.: Finite-State Online Algorithms and Their Automated Competitive Analysis. In: Asano, T. (ed.) ISAAC 2006. LNCS, vol. 4288, pp. 71–80. Springer, Heidelberg (2006)
Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problems. Journal of the ACM 22, 463–468 (1975)
Iwama, K., Taketomi, S.: Removable online knapsack problems. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 293–305. Springer, Heidelberg (2002)
Iwama, K., Zhang, G.: Optimal resource augmentations for online knapsack. In: APPROX-RANDOM 2007, pp. 180–188 (2007)
Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Heidelberg (2004)
Kao, M.-Y., Reif, J.H., Tate, S.R.: Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem. Information and Computation 131(1), 63–80 (1996); Preliminary version appeared in SODA (1993)
Lueker, G.S.: Average-case analysis of off-line and on-line knapsack problems. In: Proc. Sixth Annual ACM-SIAM SODA, pp. 179–188 (1995)
Marchetti-Spaccamela, A., Vercellis, C.: Stochastic on-line knapsack problems. Math. Programming 68(1, Ser. A), 73–104 (1995)
Motwani, R., Raghavan, P.: Randomized algorithms, ch.13 (online algorithms), Cambridge (2005)
Noga, J., Sarbua, V.: An online partially fractional knapsack problem. In: ISPAN 2005, pp. 108–112 (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Han, X., Makino, K. (2010). Online Minimization Knapsack Problem. In: Bampis, E., Jansen, K. (eds) Approximation and Online Algorithms. WAOA 2009. Lecture Notes in Computer Science, vol 5893. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-12450-1_17
Download citation
DOI: https://doi.org/10.1007/978-3-642-12450-1_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-12449-5
Online ISBN: 978-3-642-12450-1
eBook Packages: Computer ScienceComputer Science (R0)