Bin Packing with Colocations

Abstract : Motivated by an assignment problem arising in MapReduce computations, we investigate a generalization of the Bin Packing problem which we call Bin Packing with Colocations Problem. We are given a weigthed graph G = (V, E), where V represents the set of items with positive integer weights and E the set of related (to be colocated) items, and an integer q. The goal is to pack the items into a minimum number of bins so that (i) for each bin, the total weight of the items packed in this bin is at most q, and (ii) for each edge (i, j) ∈ E there is at least one bin containing both items i and j. We first point out that, when the graph is unweighted (i.e., all the items have equal weights), the problem is equivalent to the q-clique problem, and when furthermore the graph is a clique, optimal solutions are obtained from Covering Designs. We prove that the problem is strongly NP-hard even for paths and unweighted trees. Then, we propose approximation algorithms for particular families of graphs, including: a (3+ √ 5)-approximation algorithm for complete graphs (improving a previous ratio of 8), a 2-approximation algorithm for paths, a 5-approximation algorithm for trees, and an (1 + O(log q/q))-approximation algorithm for unweighted trees. For general graphs, we propose a 3 + 2mad(G)/2-approximation algorithm, where mad(G) is the maximum average degree of G. Finally, we show how to convert any approximation algorithm for Bin Packing (resp. Densest q-Subgraph) problem into an approximation algorithm for the problem on weighted (resp. unweighted) general graphs.
Type de document :
Communication dans un congrès
Klaus Jansen; Monaldo Mastrolilli. 14th International Workshop on Approximation and Online Algorithms (WAOA), Aug 2016, Aarhus, Denmark. Springer, Lecture Notes in Computer Science, 10138, pp.40-51, 2017, <http://conferences.au.dk/algo16/waoa/>. <10.1007/978-3-319-51741-4_4>
Liste complète des métadonnées


https://hal.inria.fr/hal-01435614
Contributeur : David Coudert <>
Soumis le : samedi 14 janvier 2017 - 18:59:55
Dernière modification le : samedi 18 février 2017 - 01:20:42
Document(s) archivé(s) le : samedi 15 avril 2017 - 12:17:47

Fichier

revjcb.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Jean-Claude Bermond, Nathann Cohen, David Coudert, Dimitrios Letsios, Ioannis Milis, et al.. Bin Packing with Colocations. Klaus Jansen; Monaldo Mastrolilli. 14th International Workshop on Approximation and Online Algorithms (WAOA), Aug 2016, Aarhus, Denmark. Springer, Lecture Notes in Computer Science, 10138, pp.40-51, 2017, <http://conferences.au.dk/algo16/waoa/>. <10.1007/978-3-319-51741-4_4>. <hal-01435614>

Partager

Métriques

Consultations de
la notice

222

Téléchargements du document

47