Уточнённые оценки для алгоритмов упаковки 2-гистограмм в полосу

Уточнённые оценки для алгоритмов упаковки 2-гистограмм в полосу

Назаренко С. А.
Дискретный анализ и исследование операций, 31, 4, 90-115 (2024)
Скачать статью

УДК 519.7 
DOI: 10.33048/daio.2024.31.790

Аннотация:

Рассматривается NP-трудная задача, в которой требуется упаковать гистограммы из двух столбиков в полосу минимальной длины единичной высоты. Высота каждого столбика положительная и не превосходит 1. Эта задача, называемая в англоязычной литературе Two-Bar Charts Packing Problem, является обобщением задачи упаковки в контейнеры и задачи двумерной векторной упаковки. Доказываются уточнённые оценки точности и трудоёмкости для некоторых ранее разработанных приближённых полиномиальных алгоритмов для Two-Bar Charts Packing Problem и её частных случаев. Показана достижимость этих оценок. Кроме того, рассматривается задача упаковки неограниченного числа гистограмм $k$ различных типов. При этом оценивается не длина упаковки, а её плотность, и предлагается полиномиальный алгоритм решения последней задачи в случае $k = const$. 
Ил. 12, библиогр. 26.

Литература:
  1. Erzin A. I., Plotnikov R. V., Korobkin A. P., Melidi G. E., Nazarenko S. A. Optimal investment in the development of oil and gas field // Mathematical optimization theory and operations research. Rev. Sel. Pap. 19th Int. Conf. MOTOR 2020 (Novosibirsk, Russia, July 6–10, 2020). Cham: Springer, 2020. P. 336–349. (Commun. Comput. Inf. Sci.; V. 1275).
     
  2. Erzin A. I., Melidi G. E., Nazarenko S. A., Plotnikov R. V. Two-bar charts packing problem // Optim. Lett. 2021. V. 15, No. 6. P. 1955–1971.
     
  3. Erzin A. I., Melidi G. E., Nazarenko S. A., Plotnikov R. V. A 3/2-approximation for big two-bar charts packing // J. Comb. Optim. 2021. V. 42, No. 1. P. 71–84.
     
  4. Erzin A. I., Melidi G. E., Nazarenko S. A., Plotnikov R. V. A posteriori analysis of the algorithms for two-bar charts packing problem // Advances in optimization and applications. Rev. Sel. Pap. 12th Int. Conf. OPTIMA 2021 (Petrovac, Montenegro, Sep. 27–Oct. 1, 2021). Cham: Springer, 2021. P. 201–216. (Commun. Comput. Inf. Sci.; V. 1514.)
     
  5. Erzin A. I., Kononov A. V., Melidi G. E., Nazarenko S. A. A $4/3 \times OPT + 2/3$ approximation for big two-bar charts packing problem // J. Math. Sci. 2023. V. 269, No. 6. P. 813–823.
     
  6. Erzin A. I., Kononov A. V., Nazarenko S. A., Sharankhaev K. I. An $O$($n$ log $n$)-time algorithm for linearly ordered packing of 2-bar charts into $OPT + 1$ bins // Mathematical optimization theory and operations research. Rev. Sel. Pap. 22th Int. Conf. MOTOR 2023 (Yekaterinburg, Russia, July 2–8, 2023). Cham: Springer, 2023. P. 122–133. (Commun. Comput. Inf. Sci.; V. 1881).
     
  7. Barkel M., Delorme M. Arcflow formulations and constraint generation frameworks for the two bar charts packing problem // INFORMS J. Comput. 2023. V. 35, No. 2. P. 475–494.
     
  8. Garey M. R., Johnson D. S. Computers and intractability. A guide to the theory of NP-completeness. San Francisco: Freeman, 1979. 340 p.
     
  9. Vazirani V. V. Approximation algorithms. Heidelberg: Springer, 2001. 396 p.
     
  10. Simchi-Levi D. New worst-case results for the bin-packing problem // Nav. Res. Logist. 1994. V. 41, No. 4. P. 579–585.
     
  11. Dósa G. The tight bound of first fit decreasing bin-packing algorithm is FFD(I) $\le$ 11/9 OPT(I) + 6/9 // Combinatorics, algorithms, probabilistic and experimental methodologies. Rev. Sel. Pap. 1st Int. Symp. (Hangzhou, China, Apr. 7–9, 2007). Heidelberg: Springer, 2007. P. 1–11. (Lect. Notes Comput. Sci.; V. 4614).
     
  12. Johnson D. S., Garey M. R. A 71/60 theorem for bin packing // J. Complex. 1985. V. 1, No. 1. P. 65–106.
     
  13. Yue M., Zhang L. A simple proof of the inequality MFFD(L) $\le$ 71/60 $\times$ OPT(L) + 1 for the MFFD bin-packing algorithm // Acta Math. Appl. Sin. 1995. V. 11, No. 3. P. 318–330.
     
  14. Fernandez de la Vega W., Lueker G. S. Bin packing can be solved within $1 + \epsilon$ in linear time // Combinatorica. 1981. V. 1. P. 349–355.
     
  15. Karmarkar N., Karp R. M. An efficient approximation scheme for the one dimensional bin-packing problem // 23rd Annu. Symp. Foundations of Computer Science (Chicago, USA, Nov. 3–5, 1982). Piscataway: IEEE, 1982. P. 312–320.
     
  16. Hoberg R., Rothvos T. A logarithmic additive integrality gap for bin packing // Proc. 28th Annu. ACM-SIAM Symp. Discrete Algorithms (Barcelona, Spain, Jan. 16–19, 2017). Philadelphia, PA: SIAM, 2017. P. 2616–2625.
     
  17. Kellerer H., Kotov V. An approximation algorithm with absolute worst-case performance ratio 2 for two-dimensional vector packing // Oper. Res. Lett. 2003. V. 31. P. 35–41.
     
  18. Christensen H. I., Khanb A., Pokutta S., Tetali P. Approximation and online algorithms for multidimensional bin packing: A survey // Comput. Sci. Rev. 2017. V. 24. P. 63–79.
     
  19. Bansal N., Eliáš M., Khan A. Improved approximation for vector bin packing // Proc. 27th Annu. ACM-SIAM Symp. Discrete Algorithms (Arlington, VA, USA, Jan. 10–12, 2016). Philadelphia, PA: SIAM, 2016. P. 1561–1579. 
     
  20. Woeginger G. J. There is no asymptotic PTAS for two-dimensional vector packing // Inf. Process. Lett. 1997. V. 64, No. 6. P. 293–297.
     
  21. Brucker P., Knust S. Complex scheduling. Heidelberg: Springer, 2006. 286 p.
     
  22. Goncharov E. N. A greedy heuristic approach for the resource-constrained project scheduling problem // Stud. Inform. Univers. 2011. V. 9, No. 3. P. 79–90.
     
  23. Гончаров Е. Н. Стохастический жадный алгоритм для задачи календарного планирования с ограниченными ресурсами // Дискрет. анализ и исслед. операций. 2014. Т. 21, № 3. С. 11–24.
     
  24. Hartmann S. A self-adapting genetic algorithm for project scheduling under resource constraints // Nav. Res. Logist. 2002. V. 49. P. 433–448.
     
  25. Kolisch R., Hartmann S. Experimental investigation of heuristics for resource-constrained project scheduling: An update // Eur. J. Oper. Res. 2006. V. 174. P. 23–37.
     
  26. Erzin A. I., Sharankhaev K. I. Three-bar charts packing problem // Commun. Comput. Inf. Sci. 2023. V. 1739. P. 61–75.

Исследование выполнено за счёт бюджета Новосибирского государственного университета. Дополнительных грантов на проведение или руководство этим исследованием получено не было.

Назаренко Степан Андреевич
  1. Новосибирский гос. университет, 
    ул. Пирогова, 2, 630090 Новосибирск, Россия

E-mail: s.nazarenko@g.nsu.ru

Статья поступила 15 декабря 2023 г.
После доработки — 23 апреля 2024 г.
Принята к публикации 22 июня 2024 г.

Abstract:

We consider a two-bar charts packing problem in which it is necessary to pack bar charts consisting of two bars in a unit-height strip of minimum length. Each bar has a height of at most 1 and unit length. The problem under consideration is NP-hard and generalizes the bin packing problem and two-dimensional vector packing problem. This paper proves updated accuracy estimates and time complexity for several previously developed polynomial approximation algorithms for the two-bar charts packing problem and particular cases of the problem. We show the attainability of the estimates. Furthermore, we consider a problem of packing an unlimited number of bar charts belonging to $k$ different types and propose a polynomial algorithm to solve the problem in case $k = const$. 
Illustr. 12, bibliogr. 26.

References:
  1. A. I. Erzin, R. V. Plotnikov, A. P. Korobkin, G. E. Melidi, and S. A. Nazarenko, Optimal investment in the development of oil and gas field, in Mathematical Optimization Theory and Operations Research (Rev. Sel. Pap. 19th Int. Conf. MOTOR 2020, Novosibirsk, Russia, July 6–10, 2020) (Springer, Cham, 2020), pp. 336–349 (Commun. Comput. Inf. Sci., Vol. 1275).
     
  2. A. I. Erzin, G. E. Melidi, S. A. Nazarenko, and R. V. Plotnikov, Twobar charts packing problem, Optim. Lett. 15 (6), 1955–1971 (2021).
     
  3. A. I. Erzin, G. E. Melidi, S. A. Nazarenko, and R. V. Plotnikov, A 3/2-approximation for big two-bar charts packing, J. Comb. Optim. 42 (1), 71–84 (2021).
     
  4. A. I. Erzin, G. E. Melidi, S. A. Nazarenko, and R. V. Plotnikov, A posteriori analysis of the algorithms for two-bar charts packing problem, in Advances in Optimization and Applications (Rev. Sel. Pap. 12th Int. Conf. OPTIMA 2021, Petrovac, Montenegro, Sep. 27–Oct. 1, 2021) (Springer, Cham, 2021), pp. 201–216 (Commun. Comput. Inf. Sci., Vol. 1514.)
     
  5. A. I. Erzin, A. V. Kononov, G. E. Melidi, and S. A. Nazarenko, A $4/3 \times OPT + 2/3$ approximation for big two-bar charts packing problem, J. Math. Sci. 269 (6), 813–823 (2023).
     
  6. A. I. Erzin, A. V. Kononov, S. A. Nazarenko, and K. I. Sharankhaev, An $O$($n$ log $n$)-time algorithm for linearly ordered packing of 2-bar charts into $OPT + 1$ bins, in Mathematical Optimization Theory and Operations Research (Rev. Sel. Pap. 22th Int. Conf. MOTOR 2023, Yekaterinburg, Russia, July 2–8, 2023) (Springer, Cham, 2023), pp. 122–133 (Commun. Comput. Inf. Sci., Vol. 1881).
     
  7. M. Barkel and M. Delorme, Arcflow formulations and constraint generation frameworks for the two bar charts packing problem, INFORMS J. Comput. 35 (2), 475–494 (2023).
     
  8. M. R. Garey and D. S. Johnson, Computers and Intractability. A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979).
     
  9. V. V. Vazirani, Approximation Algorithms (Springer, Heidelberg, 2001).
     
  10. D. Simchi-Levi, New worst-case results for the bin-packing problem, Nav. Res. Logist. 41 (4), 579–585 (1994). 
     
  11. G. Dósa, The tight bound of first fit decreasing bin-packing algorithm is FFD(I) $\le$ 11/9 OPT(I) + 6/9, in Combinatorics, Algorithms, Probabilistic and Experimental Methodologies (Rev. Sel. Pap. 1st Int. Symp., Hangzhou, China, Apr. 7–9, 2007) (Springer, Heidelberg, 2007), pp. 1–11 (Lect. Notes Comput. Sci., Vol. 4614). 
     
  12. D. S. Johnson and M. R. Garey, A 71/60 theorem for bin packing, J. Complex. 1 (1), 65–106 (1985).
     
  13. M. Yue and L. Zhang, A simple proof of the inequality MFFD(L) $\le$ 71/60 $\times$ OPT(L)+1 for the MFFD bin-packing algorithm, Acta Math. Appl. Sin. 11 (3), 318–330 (1995).
     
  14. W. Fernandez de la Vega and G. S. Lueker, Bin packing can be solved within $1 + \epsilon$ in linear time, Combinatorica 1, 349–355 (1981).
     
  15. N. Karmarkar and R. M. Karp, An efficient approximation scheme for the one dimensional bin-packing problem, in 23rd Annu. Symp. Foundations of Computer Science, Chicago, USA, Nov. 3–5, 1982 (IEEE, Piscataway, 1982), pp. 312–320.
     
  16. R. Hoberg and T. Rothvos, A logarithmic additive integrality gap for bin packing, in Proc. 28th Annu. ACM-SIAM Symp. Discrete Algorithms, Barcelona, Spain, Jan. 16–19, 2017 (SIAM, Philadelphia, PA, 2017), pp. 2616–2625.
     
  17. H. Kellerer and V. Kotov, An approximation algorithm with absolute worstcase performance ratio 2 for two-dimensional vector packing, Oper. Res. Lett. 31, 35–41 (2003).
     
  18. H. I. Christensen, A. Khanb, S. Pokutta, and P. Tetali, Approximation and online algorithms for multidimensional bin packing: A survey, Comput. Sci. Rev. 24, 63–79 (2017).
     
  19. N. Bansal, M. Eliáš, and A. Khan, Improved approximation for vector bin packing, in Proc. 27th Annu. ACM-SIAM Symp. Discrete Algorithms, Arlington, VA, USA, Jan. 10–12, 2016 (SIAM, Philadelphia, PA, 2016), pp. 1561–1579.
     
  20. G. J. Woeginger, There is no asymptotic PTAS for two-dimensional vector packing, Inf. Process. Lett. 64 (6), 293–297 (1997).
     
  21. P. Brucker and S. Knust, Complex Scheduling (Springer, Heidelberg, 2006).
     
  22. E. N. Goncharov, A greedy heuristic approach for the resource-constrained project scheduling problem, Stud. Inform. Univers. 9 (3), 79–90 (2011).
     
  23. E. N. Goncharov, A stochastic greedy algorithm for the resource-constrained project scheduling problem, Diskretn. Anal. Issled. Oper. 21 (3), 11–24 (2014) [Russian].
     
  24. S. Hartmann, A self-adapting genetic algorithm for project scheduling under resource constraints, Nav. Res. Logist. 49, 433–448 (2002).
     
  25. R. Kolisch and S. Hartmann, Experimental investigation of heuristics for resource-constrained project scheduling: An update, Eur. J. Oper. Res. 174, 23–37 (2006).
     
  26. A. I. Erzin and K. I. Sharankhaev, Three-bar charts packing problem, Commun. Comput. Inf. Sci. 1739, 61–75 (2023).