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

مراجع

1. AssunÇão, R.M., Neves, M.C., Câmara G. and Da Costa Freitas C.Effcient regionalization techniques for socio‐economic geographical units using minimum spanning trees, Int. J. Geogr. Inf. Sci. 20 (7) (2006) 797–811.
2. Bansal, N., Liu, Z. and Sankar, A. Bin-packing with fragile objects and frequency allocation in cellular networks, Wireless Netw. 15, (2009) 821–830.

3. Böhm, M., Dósa, G., Epstein, L., Sgall, J. and Veselý, P. Colored bin packing: Online algorithms and lower bounds, Algorithmica 80 (1) (2018) 155–184.
4. Chataigner, F., Salgado, L.R.B. and Wakabayashi, Y. Approximation and inapproximability results on balanced connected partitions of graphs, Discrete Math. Theor. Comput. Sci. 9 (1) (2007) 177–192.
5. Clautiaux, F., Guillot, J. and Pesneau, P. Exact approaches for solving a covering problem with capacitated subtrees, Comput. Oper. Res. 105 (2019) 85–101.
6. Dell’Amico, M., Díaz Díaz, J.C. and Iori, M. The bin packing problem with precedence constraints, Oper. Res. 60 (6) (2012) 1491–1504.
7. Dósa, G. The tight bound of first fit decreasing bin-packing algorithm is FFD(I) ff 11/9OPT(I) + 6/9 Chen B., Paterson M., Zhang G. (eds) Combinatorics, Algorithms, Probabilistic and Experimental Methodologies. ESCAPE 2007. Lecture Notes in Computer Science, vol 4614. Springer, Berlin, Heidelberg, 2007.
8. Dósa, G. and Sgall, J. First fit bin packing: a tight analysis, 30th International Symposium on Theoretical Aspects of Computer Science, 538–549, LIPIcs. Leibniz Int. Proc. Inform., 20, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2013.
9. Garey, M.R. and Johnson, D.S. Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman & Co., New York, NY, USA, 1979.
10. Ito, T., Uno, T., Zhou, X. and Nishizeki, T. Partitioning a weighted tree to subtrees of almost uniform size, Algorithms and computation, 196–207, Lecture Notes in Comput. Sci., 5369, Springer, Berlin, 2008.
11. Ito, T., Zhou, X. and Nishizeki, T. Partitioning a graph of bounded treewidth to connected subgraphs of almost uniform size, J. Discrete Algorithms 4 (1) (2006) 142–154.
12. Jansen, K. An approximation scheme for bin packing with conflicts, J. Comb. Optim. 3 (4) (1999) 363–377.
13. Vazirani, V.V. Approximation algorithms, Berlin: Springer, 2003.