Algorithmic Analysis of Priority-Based Bin Packing

7th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM 2021 -- 11 February 2021 through 13 February 2021 -- 253869
This paper is concerned with a new variant of Traditional Bin Packing (TBP) called Priority-Based Bin Packing with Subset Constraints (PBBP-SC). In a TBP instance, we are given a collection of items { a1, a2, … an}, with ai? (0, 1 ) and a collection of unit-size bins { B1, B2, …, Bm}. One problem associated with TBP is the bin minimization problem. The goal of this problem is to pack the items in as few bins as possible. In a PBBP-SC instance, we are given a collection of unit-size items and a collection of bins of varying capacities. Associated with each item is a positive integer which is called its priority. The priority of an item indicates its importance in a (possibly infeasible) packing. As with the traditional case, these items need to be packed in the fewest number of bins. What complicates the problem is the fact that each item can be assigned to only one of a select set of bins, i.e., the bins are not interchangeable. We investigate several problems associated with PBBP-SC. Checking if there is a feasible assignment to a given instance is one problem. Finding a maximum priority assignment in case of the instance being infeasible is another. Finding an assignment with the fewest number of bins to pack a feasible instance is a third. We derive a number of results from both the algorithmic and computational complexity perspectives for these problems. © 2021, Springer Nature Switzerland AG.
FA9550-19-1-0177; Air Force Research Laboratory, AFRL: FA8750-17-S-7007
This research is supported in part by the Air-Force of Scientific Research through Grant FA9550-19-1-0177 and in part by the Air-Force Research Laboratory, Rome through Contract FA8750-17-S-7007.