Connected bin packing problem on traceable graphs

Document Type : Original Article

Authors

• A. Nejoomi
• A. Dolati

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

10.22067/ijnao.2021.67913.1010

Abstract

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.

Keywords

• Bin Packing Problem
• Connectivity
• Complexity Theory
• Approximation Algorithms

20.1001.1.24236977.2022.12.1.8.2

Main Subjects

• Control and Optimization

---

References

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.