@inproceedings{d80c8997d6fb499caa729c898564e5bd,
title = "A Posteriori Analysis of the Algorithms for Two-Bar Charts Packing Problem",
abstract = "The Two-Bar Charts Packing Problem (2-BCPP) is to pack the bar charts (BCs) of two bars into the horizontal unit-height strip of minimal length. The bars may move vertically within the strip, but it is forbidden to change the order and separate the chart{\textquoteright}s bars. Recently, for this novel issue, which is a generalization of the Bin Packing Problem (BPP), Strip Packing Problem (SPP), and 2-Dimensional Vector Packing Problem (2-DVPP), several approximation algorithms with guaranteed estimates have been proposed. However, after a preliminary analysis of the solutions constructed by approximation algorithms, we discerned that the guaranteed estimates are inaccurate. This fact inspired us to conduct a numerical experiment in which the approximate solutions are compared to each other and with the optimal ones. We use the Boolean Linear Programming (BLP) formulation of 2-BCPP proposed earlier and apply the CPLEX package to find the optimal solutions or lower bounds for optimum. We also use a database of instances for BPP with known optimal solutions to construct the instances for the 2-BCPP with known minimal packing length. The results of computational experiments comprise the main content of this paper.",
keywords = "Approximation algorithms, Bar charts, Simulation, Strip packing",
author = "Adil Erzin and Georgii Melidi and Stepan Nazarenko and Roman Plotnikov",
note = "Funding Information: The study was carried out within the framework of the state contract of the Sobolev Institute of Mathematics (project no. 0314–2019–0014). Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; 12th International Conference on Optimization and Applications, OPTIMA 2021 ; Conference date: 27-09-2021 Through 01-10-2021",
year = "2021",
doi = "10.1007/978-3-030-92711-0_14",
language = "English",
isbn = "978-3-030-92710-3",
series = "Communications in Computer and Information Science",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "201--216",
editor = "Olenev, {Nicholas N.} and Evtushenko, {Yuri G.} and Vlasta Malkova and Milojica Jacimovic and Michael Khachay",
booktitle = "Advances in Optimization and Applications - 12th International Conference, OPTIMA 2021, Revised Selected Papers",
address = "Germany",
}