Connected bin packing problem on traceable graphs
عنوان مقاله: Connected bin packing problem on traceable graphs
شناسه ملی مقاله: JR_IJNAO-12-1_008
منتشر شده در در سال 1401
شناسه ملی مقاله: JR_IJNAO-12-1_008
منتشر شده در در سال 1401
مشخصات نویسندگان مقاله:
A. Nejoomi - Department of Computer Science, Shahed University, Tehran, Iran.
A. Dolati - Department of Computer Science, Shahed University, Tehran, Iran.
خلاصه مقاله:
A. Nejoomi - Department of Computer Science, Shahed University, Tehran, Iran.
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 ۲ 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 ۲.
کلمات کلیدی: Bin Packing Problem, Connectivity, Complexity theory, Approximation Algorithms
صفحه اختصاصی مقاله و دریافت فایل کامل: https://civilica.com/doc/1424909/