A 3/2--approximation for big two-bar charts packing

Adil Erzin; Stepan Nazarenko; Gregory Melidi; Roman Plotnikov

paper

A 3/2--approximation for big two-bar charts packing

arXiv:2006.10361

Abstract

We consider a Two-Bar Charts Packing Problem (2-BCPP), in which it is necessary to pack two-bar charts (2-BCs) in a unit-height strip of minimum length. The problem is a generalization of the Bin Packing Problem (BPP). Earlier, we proposed an $O (n^{2})$ -time algorithm that constructs the packing which length at most $2 \cdot O P T + 1$ , where $O P T$ is the minimum length of the packing of $n$ 2-BCs. In this paper, we propose an $O (n^{4})$ -time 3/2-approximate algorithm when each BC has at least one bar greater than 1/2.