On on-line algorithms for Bin, Strip and Box Packing, and their worstand average-case analysis
https://doi.org/10.15514/ISPRAS-2018-30(4)-14
Abstract
About the Authors
D. O. LazarevRussian Federation
N. N. Kuzjurin
Russian Federation
References
1. Massobrio R., Nesmachnow S., Tchernykh A., Avetisyan A., Radchenko G. Towards a Cloud Computing Paradigm for Big Data Analysis in Smart Cities. Trudy ISP RAN/Proc.ISP RAS, vol. 28, issue 6, 2016. pp. 121-140 (in Russian). DOI: 10.15514/ISPRAS-2016-28(6)-9
2. Anichkin A.S., Semenov V.A. Mathematical formalization of project scheduling problems. Trudy ISP RAN/Proc. ISP RAS, vol. 29, issue 2, 2017. pp. 231-256 (in Russian). DOI: 10.15514/ISPRAS-2017-29(2)-9
3. Zelenova S.A., Zelenov S.V. Non-conflict scheduling criterion for strict periodic tasks. Trudy ISP RAN/Proc. ISP RAS, vol. 29, issue 6, 2017. pp. 183-202 (in Russian). DOI: 10.15514/ISPRAS-2017-29(6)-10
4. Ghalam L., Grosu D. A Parallel Approximation Algorithm for Scheduling Identical Machines. In IEEE International Parallel and Distributed Processing Symposium Workshops, 2017, pp. 619-628
5. Sheikhalishahi M., Wallace R. M., Grandinetti L., Vazquez-Poletti J. L., Guerriero F. A multi-dimensional job scheduling. Future Generation Computer Systems, vol. 54, 2016, pp. 123-131
6. Tchernykh A., Schwiegelshohn U., Yahyapour R., Kuzjurin N. On-line hierarchical job scheduling on grids with admissible allocation. Journal of Scheduling, 2010, vol. 13, issue 5, pp. 545-552
7. Tshernykh A., Ramirez J.M., Avetisyan A., Kuzjurin N., Grushin D., Zhuk S. Two-Level Job-Scheduling strategies for a Computational Grid. Lecture Notes in Computer Science book series, vol. 3911, pp. 774-781
8. Cohil B., Shah S., Goleshha Y., Patel D. A Comparative Analysis of Virtual Machine Placement Techniques in the Cloud Environment. International Journal of Computer Applications, vol. 156, no. 14, 2016, pp. 12-18
9. Garey M.R., Johnson D.S. Computers and intractability: a guide to the theory of NP-completeness. Freeman: San Francisco, 1979, 338 p.
10. Johnson D.S. Near-optimal Bin Packing Algorithms. PhD Thesis, Massachusetts Institute of Technology, Department of Mathematics, Cambridge, 1973. 401 p.
11. Johnson D.S., Demers A., Ullman J.D., Garey M.R., Graham R.L. Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms. SIAM Journal on computing, vol. 3, issue 4, 1974, pp. 299- 325
12. Garey M.R. Graham R.L., Ullman J.D., Worst-case analysis of memory allocation algorithms. Proceedings of the fourth annual ACM symposium on theory of computing. 1972, pp. 143-150
13. Garey M.R., Graham R.L., Johnson D.S., Yao A.C. Resource constrained scheduling as generalized bin packing. Journal of Combinatorial Theory, Series A, vol. 21, issue 3, 1976, pp. 257-298
14. Yao A.C. New Algorithms for Bin Packing. Journal of the ACM, vol. 27, issue 2, 1981, pp. 207-227
15. Gambosi G., Postiglione a., Talamo M.M. New algorithms for online Bin Packing. In Proceedings of the First Italian Conference on Algorithms and Complexity, 1990, pp. 44-59
16. Ivcović Z. and Lloyd E. Fully dynamic algorithms for Bin Packing: Being (mostly) myopic helps. Lecture Notes in Computer Science, vol. 726, pp. 224-235
17. Seiden S.S. On the Online Bin Packing Problem. Lecture Notes in computer science, vol. 2076, 2002, pp. 207-227
18. Brown J.D. A lower Bound for On-Line One Dimensional Bin Packing Algorithms. Technical Report R-864, coordinated Science laboratory, University of Illinois, Urbana, IL, 1979.
19. Vliet A. An improved lower bound for on-line bin packing algorithms. Information Processing Letters, vol. 43, issue 5, 1992, pp. 277-284
20. Breitgand D., Epstein A. Improving consolidations of virtual machines with risk-aware Bandwidth oversubscription in compute clouds. In Proceedings of the IEEE INFCOM, 2012, pp. 2861-2865
21. Ajtai M., Komlós J., Tusnadi G. On Optimal Matchings. Combinatorica, vol. 4, issue 4, 1984, pp. 259-264
22. Karp R.M., Luby M., Marchetti-Spaccamela A. A probabilistic analysis of multidimensional bin packing problem. In Proceedings of the sixteen annual ACM symposium on theory of computing, 1984, pp.289-298
23. Coffman E.G., Shor P.W. A Simple Proof of the sqrt(n log3/4 n) Upright Matching Bound. SIAM Journal on Discrete Mathematics, vol. 4, issue 1, 1991, pp. 48-57
24. Shor P.W. The average-case analysis of some on-line algorithms for bin packing. Combinatorica, vol. 6, issue 4, 1986, pp. 179-200
25. Leighton F.T., Shor P. Tight bonds for minimax grid matching, with application to the average-case analysis of algorithms. In Proceedings of the eighteenth Annual ACM symposium on theory of computing, 1986 , pp. 91-103
26. Coffman E.G., Courcoubetis C., Garey M.R., Johnson D.S., McGeoch L.A., Shor P.W., Weber R. and Yannakakis M. Fundamental discrepancies between average-case analysis under discrete and continuous distributions: a bin packing study. In Proceedings of the Twenty-first Annual ACM symposium on theory of computing, 1991, pp. 230-240
27. Shor P.W. How to pack better than Best Fit: tight bounds for average-case online Bin Packing. In Proceedings 32nd of the Annual Symposium of foundations of Computer Science, 1991, pp. 752-759
28. Galambos G., A. van Vliet. Lower bounds for 1-, 2-, and 3- dimensional on-line bin packing algorithms. Computing, vol. 52, issue 3, 1994, pp. 281-297
29. Han X., Chin F.Y.L., Ting H.-F., Zhang G., Zhang Y. A new upper bound 2.5545 on 2D Online Bin Packing. ACM Transactions on algorithms, vol. 7, issue 4, 2011, article No. 50
30. Csirik J., A. van Vliet. An on-line algorithm for multidimensional bin packing. Operation Research Letters, vol. 13, issue 3, 1993, pp. 149-158
31. Epstein l., R. van Stee. Optimal Online Algorithms for Multidimensional Packing Problems. In Proceedings of the Fifteenth Annual ACM-CIAM Symposium on Discrete algorithms, 2004, pp. 214-223
32. Chang E-C, Wang W., Kankanhalli M.S. Multidimensional on-line bin-packing: An algorithm and it’s average-case analysis. Information Processing Letters, vol. 48, issue 3, 1993, pp. 121-125
33. Baker B.S., Coffman E.G., Rivest R.L. Orthogonal Packings in Two Dimensions. SIAM Journal on Computing, vol. 9, issue 4, 1980, pp. 846-855
34. Baker B.S., Schwarz J.S. Shelf algorithms for two-dimensional packing problems. SIAM Journal on Computing, vol. 12, issue 3, 1983, pp. 508-525
35. Csirik J., Woeginger G.J. Shelf algorithms for on-line strip packing. Information Processing Letters, vol. 63, issue 4, 1997, pp. 171-175
36. Han X., Iwama K., Ye d., Zhang G. Strip Packing vs Bin Packing. Lecture Notes in Computer Science, vol. 4508, 2007, pp. 358-367
37. Coffman E.G., Shor P.W. Packing in two dimensions: Asymptotic average-case analysis of algorithms. Algorithmica, vol. 9, issue 3, 1993, pp. 253-277
38. Kuzjurin N.N., Pospelov A.I. Probabilistic analysis of different shelf algorithms for packing rectangles into a strip. Trudy ISP RAN/Proc. ISP RAS, vol. 12, 2007, pp. 17-26 (in Russian)
39. Kuzyurin N.N., Pospelov A.I. Probabilistic analysis of a new class of strip packing algorithms. Comput. Math. and Math. Phys., vol. 51, issue 10, 2011, article no. 1817
40. Trushnikov M.A. On one problem of Koffman-Shor connected to strip packing problem. Trudy ISP RAN/Proc. ISP RAS, vol. 22, 2012, pp. 456-462 (in Russian). DOI: 10.15514/ISPRAS-2012-22-24
41. Trushnikov M.A. Probabilistic analysis of a new strip packing algorithm. Trudy ISP RAN/Proc. ISP RAS, vol. 24, 2013, str. 457-468 (in Russian). DOI: 10.15514/ISPRAS-2013-24-21
42. Lazarev D.O., Kuzyrin N.N. An algorithm for Multiple Strip Package and its average case evaluation. Trudy ISP RAN/Proc. ISP RAS, vol. 29, issue 6, 2017. pp. 221-228 (in Russian). DOI: 10.15514/ISPRAS-2017-29(6)-13
43. Kuzjurin N.N., Grushin D.A., Fomin A. Two-dimensional packing problems and optimization in distributed computing systems. Trudy ISP RAN/Proc. ISP RAS, vol. 26, issue 1, 2014, pp. 483-502 (in Russian). DOI: 10.15514/ISPRAS-2014-26(1)-21
44. Ye D., Han X., Zhang G. Online multiple-strip packing. Theoretical Computer Science, vol. 412, issue 3, 2011, pp. 233-239
45. Zhuk S.N. Approximation algorithms for packing rectangles into several strips. Discrete Mathematics and Applications, vol. 16, issue 1, 2006, pp. 73-85
46. Zhuk S.N. Analysis of some heuristics of packing rectangles into several strips. Trudy ISP RAN/Proc. ISP RAS, vol. 6, 2004, pp. 13-26 (in Russian)
47. Zhuk S.N. Online algorithm for packing rectangles into several strips with guaranteed accuracy estimates. Trudy ISP RAN/Proc. ISP RAS, vol. 12, 2007, pp. 7-16 (in Russian)
48. Zhuk S.N. On-line algorithms for packing rectangles into several strips. Discrete Mathematics and Applications, vol. 17, issue 5, 2007, pp. 517-531
49. Zhuk S.N. On-line algorithm for scheduling parallel tasks on a group of related clusters. Trudy ISP RAN/Proc. ISP RAS, vol. 23, 2012, pp. 447-454 (in Russian). DOI: 10.15514/ISPRAS-2012-23-27
Review
For citations:
Lazarev D.O., Kuzjurin N.N. On on-line algorithms for Bin, Strip and Box Packing, and their worstand average-case analysis. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2018;30(4):209-230. (In Russ.) https://doi.org/10.15514/ISPRAS-2018-30(4)-14