Efficient Lower Bounds for Packing Problems in Heterogeneous Bins with Conflicts Constraint - Université d'Artois Accéder directement au contenu
Chapitre D'ouvrage Année : 2016

Efficient Lower Bounds for Packing Problems in Heterogeneous Bins with Conflicts Constraint

Résumé

In this paper we discuss a version of the classical one dimensional bin-packing problem, where the objective is to minimize the total cost of heterogeneous bins needed to store given items, each with some space requirements. In this version, some of the items are incompatible with each other, and cannot be packed together. This problem with various real world applications generalizes both the Variable Sized Bin Packing Problem and the Vertex Coloring Problem. We propose two lower bounds for this problem based on both the relaxation of the integrity constraints and the computation of the large clique in the conflicts graph.\n\n
Fichier non déposé

Dates et versions

hal-03301156 , version 1 (27-07-2021)

Identifiants

  • HAL Id : hal-03301156 , version 1

Citer

Mohamed Maiza, Mohammed Said Radjef, Lakhdar Saïs. Efficient Lower Bounds for Packing Problems in Heterogeneous Bins with Conflicts Constraint. Anastassiou G. and Duman O. Intelligent Mathematics II : Applied Mathematics and Approximation Theory, 441, Springer, 2016. ⟨hal-03301156⟩
16 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More