# Bin packing with colocations

1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
2 GALaC - LRI - Graphes, Algorithmes et Combinatoire (LRI)
LRI - Laboratoire de Recherche en Informatique
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. Given a set V of items with positive integer weights, an underlying graph G = (V, E), and an integer q, the goal is to pack the items into a minimum number of bins so that (i) the total weight of the items packed in every 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 show that when the underlying graph is unweighted (i.e., all the items have equal weights), the problem is equivalent to the q-clique problem, and when furthermore the underlying graph is a clique, optimal solutions are obtained from covering designs. We prove that the problem becomes NP-hard even for weighted paths and un-weighted trees and we propose approximation algorithms for particular families of graphs, including: a (3 + √ 5)-approximate algorithm for weighted complete graphs (improving a previous 8-approximation), a 2-approximate algorithm for weighted paths, a 5-approximate algorithm for weighted trees, and an (1+)-approximate algorithm for unweighted trees. For general weighted graphs, we propose a 3 + 2mad(G)/2-approximate algorithm, where mad(G) is the maximum average degree of G. Finally, we show how to convert any ρ-approximation algorithm for the Bin Packing (resp. the Densest q-Subgraph problem) into an approximation algorithm for the problem on weighted (resp. unweighted) general graphs.
Type de document :
Rapport
[Research Report] Inria; I3S. 2016

Littérature citée [13 références]

https://hal.inria.fr/hal-01381333
Contributeur : David Coudert <>
Soumis le : samedi 17 mars 2018 - 20:01:57
Dernière modification le : lundi 30 avril 2018 - 14:30:10

### Fichier

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

### Citation

Jean-Claude Bermond, Nathann Cohen, David Coudert, Dimitrios Letsios, Ioannis Milis, et al.. Bin packing with colocations. [Research Report] Inria; I3S. 2016. 〈hal-01381333v2〉

### Métriques

Consultations de la notice

## 287

Téléchargements de fichiers