A 4/3· OPT+2/3 approximation for big two-bar charts packing problem
share
Two-Bar Charts Packing Problem is to pack n two-bar charts (2-BCs) in a minimal number of unit-capacity bins. This problem generalizes the strongly NP-hard Bin Packing Problem. We prove that the problem remains strongly NP-hard even if each 2-BC has at least one bar higher than 1/2. Next we consider the case when the first (or second) bar of each 2-BC is higher than 1/2 and show that the O(n^2)-time greedy algorithm with preliminary lexicographic ordering of 2-BCs constructs a packing of length at most OPT+1, where OPT is optimum. Eventually, this result allowed us to present an O(n^2.5)-time algorithm that constructs a packing of length at most 4/3· OPT+2/3 for the NP-hard case when each 2-BC has at least one bar higher than 1/2.
READ FULL TEXT