摘要: We investigate the online variant of Multiple Knapsack problem: an algorithm is to pack items, arbitrary sizes and profits, in k knapsacks (bins) without exceeding capacity any bin. study two objective functions: sum maximum profits over all bins. Both have been studied before restricted variants our Dual Bin Packing [1], Removable [7, 8]. Following these, we variants, depending on whether allowed remove (forever) items from its bins or not, special cases where profit item a function size, addition general setting.
springer.com
sci-hub.st 参考文章(13)
Yossi Azar, Ety Khaitsin, Prompt mechanism for ad placement over time algorithmic game theory. pp. 19- 30 ,(2011) , 10.1007/978-3-642-24829-0_4
Hans-Joachim Böckenhauer, Dennis Komm, Richard Královič, Peter Rossmanith, On the advice complexity of the knapsack problem latin american symposium on theoretical informatics. pp. 61- 72 ,(2012) , 10.1007/978-3-642-29344-3_6
Ran El-Yaniv, Allan Borodin, Online Computation and Competitive Analysis ,(1998)
Kazuo Iwama, Shiro Taketomi, Removable Online Knapsack Problems international colloquium on automata languages and programming. pp. 293- 305 ,(2002) , 10.1007/3-540-45465-9_26
A. Marchetti-Spaccamela, C. Vercellis, Stochastic on-line knapsack problems Mathematical Programming. ,vol. 68, pp. 73- 104 ,(1995) , 10.1007/BF01585758
Azar, Boyar, Favrholdt, Larsen, Nielsen, Epstein, Fair versus Unrestricted Bin Packing Algorithmica. ,vol. 34, pp. 181- 196 ,(2002) , 10.1007/S00453-002-0965-6
Kazuo Iwama, Guochuan Zhang, Online knapsack with resource augmentation Information Processing Letters. ,vol. 110, pp. 1016- 1020 ,(2010) , 10.1016/J.IPL.2010.08.013
George S. Lueker, Average-case analysis of off-line and on-line knapsack problems symposium on discrete algorithms. ,vol. 29, pp. 179- 188 ,(1995) , 10.5555/313651.313692
S. Ben-David, A. Borodin, R. Karp, G. Tardos, A. Wigderson, On the power of randomization in on-line algorithms Algorithmica. ,vol. 11, pp. 2- 14 ,(1994) , 10.1007/BF01294260
Chandra Chekuri, Iftah Gamzu, Truthful Mechanisms via Greedy Iterative Packing Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. ,vol. 5687, pp. 56- 69 ,(2009) , 10.1007/978-3-642-03685-9_5