  We consider the Bin Packing problem with a partition matroid constraint. The
input is a set of items of sizes in $(0,1]$, and a partition matroid over the
items. The goal is to pack all items in a minimum number of unit-size bins,
such that each bin forms an independent set in the matroid. The problem is a
generalization of both Group Bin Packing and Bin Packing with Cardinality
Constraints. Bin Packing with Partition Matroid naturally arises in resource
allocation to ensure fault tolerance and security, as well as in harvesting
computing capacity. Our main result is a polynomial-time algorithm that packs
the items in $OPT + o(OPT)$ bins, where OPT is the minimum number of bins
required for packing the given instance. This matches the best known result for
the classic Bin Packing problem up to the function hidden by o(OPT). As special
cases, our result improves upon the existing APTAS for Group Bin Packing and
generalizes the AFTPAS for Bin Packing with Cardinality Constraints. Our
approach is based on rounding a solution for a configuration-LP formulation of
the problem. The rounding takes a novel point of view of prototypes in which
items are interpreted as placeholders for other items and applies fractional
grouping to modify a fractional solution (prototype) into one having nice
integrality properties.
