Updated estimates for algorithms for packing $2$-bar charts in a strip

S. A. Nazarenko

Diskretnyj analiz i issledovanie operacij, Tome 31 (2024) no. 4, pp. 90-115

Résumé

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 = \text{const}.$ Illustr. 12, bibliogr. 26.

Détail

Keywords: bar chart, strip packing, NP-hard problem, a priori estimate, attainability.

Bibliographie

[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), Commun. Comput. Inf. Sci., 1275, Springer, Cham, 2020, 336–349 | MR

[2] Erzin A. I., Melidi G. E., Nazarenko S. A., Plotnikov R. V., “Two-bar charts packing problem”, Optim. Lett., 15:6 (2021), 1955–1971 | DOI | MR

[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., 42:1 (2021), 71–84 | DOI | MR

[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), Commun. Comput. Inf. Sci., 1514, Springer, Cham, 2021, 201–216 | MR

[5] Erzin A. I., Kononov A. V., Melidi G. E., Nazarenko S. A., “A ${4}/{3}\times\text{OPT} + {2}/{3}$ approximation for big two-bar charts packing problem”, J. Math. Sci., 269:6 (2023), 813–823 | DOI | MR

[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 $\text{OPT} + 1$ bins”, Mathematical optimization theory and operations research, Rev. Sel. Pap. 22th Int. Conf. MOTOR 2023 (Yekaterinburg, Russia, July 2–8, 2023), Commun. Comput. Inf. Sci., 1881, Springer, Cham, 2023, 122–133 | MR

[7] Barkel M., Delorme M., “Arcflow formulations and constraint generation frameworks for the two bar charts packing problem”, INFORMS J. Comput., 35:2 (2023), 475–494 | DOI | MR

[8] Garey M. R., Johnson D. S., Computers and intractability. A guide to the theory of NP-completeness, Freeman, San Francisco, 1979, 340 pp. | MR

[9] Vazirani V. V., Approximation algorithms, Springer, Heidelberg, 2001, 396 pp. | MR

[10] Simchi-Levi D., “New worst-case results for the bin-packing problem”, Nav. Res. Logist, 41:4 (1994), 579–585 | 3.0.CO;2-G class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR

[11] Dósa G., “The tight bound of first fit decreasing bin-packing algorithm is $\text{FFD}(I)\leq 11/9~\text{OPT}(I)+6/9$”, Combinatorics, algorithms, probabilistic and experimental methodologies, Rev. Sel. Pap. 1st Int. Symp. (Hangzhou, China, Apr. 7–9, 2007), Lect. Notes Comput. Sci., 4614, Springer, Heidelberg, 2007, 1–11 | DOI

[12] Johnson D. S., Garey M. R., “A \(71/60\) theorem for bin packing”, J. Complex, 1:1 (1985), 65–106 | DOI | MR

[13] Yue M., Zhang L., “A simple proof of the inequality $\text{MFFD}(L)\leq 71/60\times\text{OPT}(L)+1$ for the MFFD bin-packing algorithm”, Acta Math. Appl. Sin, 11:3 (1995), 318–330 | DOI | MR

[14] Fernandez de la Vega W., Lueker G. S., “Bin packing can be solved within $1+\varepsilon$ in linear time”, Combinatorica, 1 (1981), 349–355 | DOI | MR

[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), IEEE, Piscataway, 1982, 312–320 | DOI | MR

[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), SIAM, Philadelphia, PA, 2017, 2616–2625 | DOI | MR

[17] Kellerer H., Kotov V., “An approximation algorithm with absolute worst-case performance ratio 2 for two-dimensional vector packing”, Oper. Res. Lett., 31 (2003), 35–41 | DOI | MR

[18] Christensen H. I., Khanb A., Pokutta S., Tetali P., “Approximation and online algorithms for multidimensional bin packing: A survey”, Comput. Sci. Rev., 24 (2017), 63–79 | DOI | MR

[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), SIAM, Philadelphia, PA, 2016, 1561–1579 | DOI | MR

[20] Woeginger G. J., “There is no asymptotic PTAS for two-dimensional vector packing”, Inf. Process. Lett., 64:6 (1997), 293–297 | DOI | MR

[21] Brucker P., Knust S., Complex scheduling, Springer, Heidelberg, 2006, 286 pp. | MR

[22] Goncharov E. N., “A greedy heuristic approach for the resource-constrained project scheduling problem”, Stud. Inform. Univers., 9:3 (2011), 79–90

[23] E. N. Goncharov, “A stochastic greedy algorithm for the resource-constrained project scheduling problem”, Diskretn. Anal. Issled. Oper., 21:3 (2014), 11–24 (In Russian) | MR

[24] Hartmann S., “A self-adapting genetic algorithm for project scheduling under resource constraints”, Nav. Res. Logist, 49 (2002), 433–448 | DOI | MR

[25] Kolisch R., Hartmann S., “Experimental investigation of heuristics for resource-constrained project scheduling: An update”, Eur. J. Oper. Res., 174 (2006), 23–37 | DOI

[26] Erzin A. I., Sharankhaev K. I., “Three-bar charts packing problem”, Commun. Comput. Inf. Sci., 1739 (2023), 61–75 | MR