Connected Bin Packing Problem on Traceable Graphs

We consider a new extension of the bin packing problem in which a set of connectivity constraints should be satisfied. an undirected graph with a weight function on the nodes is given. the objective is to pack all the nodes in the minimum number of unitcapacity bins, such that the induced subgraph on the set of nodes packed in each bin is connected. after analyzing some structural properties of the problem, we present a linear time approximation algorithm for this problem when the underlying graph is traceable. we show that the approximation factor of this algorithm is 2 and this factor is tight. finally, concerning the investigated structural properties, we extend the algorithm for more general graphs. this extended algorithm also has a tight approximation factor of 2.