Is the flexible bin packing problem NP-complete?

Question

I am currently trying to figure out whether a flavor of the bin packing problem, which I call the "flexible bin packing problem" (F-BPP), is NP-complete.

Here are the definitions for the traditional bin packing problem (BPP) and the flexible bin packing problem (F-BPP):

Bin packing problem (BPP):

Optimization problem: Given a set of n items and their corresponding volumes (the volume of each item is between 0 and 1), pack the n items into the minimum number of bins (each with capacity 1) such that the capacity of each bin is not exceeded (https://ics.uci.edu/~goodrich/teach/cs165/notes/BinPacking.pdf).

Decision problem: Given a set of n items and their corresponding volumes (the volume of each item is between 0 and 1), and an integer k, determine if it is possible to pack all n items into at most k bins, each with capacity 1, such that the capacity of each bin is not exceeded. This problem is NP-complete (https://ics.uci.edu/~goodrich/teach/cs165/notes/BinPacking.pdf).

Flexible bin packing problem (F-BPP):

Decision problem: Given n item types, m bin types, and a mapping between compatible item type and bin type pairs (the pairs are keys in the mapping) and the volume (between 0 and 1) of an item of that type in a bin of that type (the volumes are values in mapping), and an integer k >= m, determine if it is possible to pack at least one item of each type in at most k bins, where each bin has capacity 1, the capacity of each bin is not exceeded, and all bin types are used at least once. Items and bin types can be used more than once.

Answer 1

Here is a potential solution that I came up with for the above problem.

Could someone please verify my explanation for why F-BPP is in NP and my reduction of BPP to F-BPP?

Proof:

F-BPP is in NP: Suppose that a solution to F-BPP is a list of 2-tuples, where each 2-tuple corresponds to a bin. The first value of the 2-tuple is the bin type, and the second value of the 2-tuple is a key-value mapping between each item type and the number of items of that type that are in the bin.

A solution to F-BPP in this form can be verified in polynomial time by iterating through each bin and the items in those bins. As we iterate, we can count the number of bins. If the number of bins exceeds k, then the solution is invalid. Hence, iterating through the bins takes O(k) time. For each bin, we can iterate through the n key-value pairs in its mapping, and check that the collective volume of those items does not exceed the capacity of the bin. This takes O(n) time. The total time complexity of iterating through the bins and items in each bin is O(nk) time. As we iterate, we can keep track of the unique item types and bin types observed. Once the iterations are done, it takes O(n) time to check that all unique item types have been used and it takes O(m) time to check that all unique bin types have been used. Hence, it takes polynomial time to verify a solution to F-BPP, so F-BPP is in NP.

Reduction from BPP to F-BPP: Given the inputs to BPP, each of the n items corresponds to its own item type (n item types). Keep the same integer k. All bins are of one type, so m = 1. Create the mapping between each item type and the one bin type, where the volume for each item type under the one bin type is the same as the volume of the corresponding item in BPP. The BPP inputs, the one bin type, the mapping, and the integer k are now the inputs to the F-BPP problem. The capacity of each bin is still 1.

If the answer to F-BPP is yes, then the answer to BPP is also yes, since there is only one type of bin used, items of all types were packed, and the item volumes and bin capacities remained the same.

Since each item in BPP can only be used once, items can be removed from the F-BPP packing such that only one item of each type remains, and this will not increase the bin count (number of bins is still at most k). By design, since only one bin type is used, the F-BPP bin packing should not need to use more than one item of a given type (since the one bin type will be covered from using each item type once), but in case such duplicate items exist, they can simply be removed without increasing the bin count.

The resulting bin packing is the bin packing for BPP. Hence, BPP is reducible in polynomial time to F-BPP.

Result: Since F-BPP is in NP and BPP is polynomial-time reducible to F-BPP, F-BPP is also NP-complete.