Updated Estimates for Algorithms for Packing2-Bar Charts in a Strip

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 different types and propose a polynomial algorithm to solve the problem in case .