Connected bin packing problem on traceable graphs

Iranian Journal of Numerical Analysis and Optimization

دوره 12، شماره 1 - شماره پیاپی 21، خرداد 2022، صفحه 163-171   

نوع مقاله: Original Article

شناسه دیجیتال (DOI): 10.22067/ijnao.2021.67913.1010

نویسندگان

A. Nejoomi؛ A. Dolati^*

Department of Computer Science, Shahed University, Tehran, Iran.

چکیده

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.

کلیدواژه‌ها

Bin Packing Problem؛ Connectivity؛ Complexity Theory؛ Approximation Algorithms

مراجع