%0 Journal Article
%T Connected bin packing problem on traceable graphs
%J Iranian Journal of Numerical Analysis and Optimization
%I Ferdowsi University of Mashhad
%Z 2423-6977
%A Nejoomi, A.
%A Dolati, A.
%D 2022
%\ 03/01/2022
%V 12
%N 1
%P 163-171
%! Connected bin packing problem on traceable graphs
%K Bin Packing Problem
%K Connectivity
%K Complexity theory
%K Approximation Algorithms
%R 10.22067/ijnao.2021.67913.1010
%X 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 unit-capacity 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.
%U https://ijnao.um.ac.ir/article_40635_e5f368461d145a66208acf1635aeba83.pdf