Skip to Main content Skip to Navigation
Book sections

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

Abstract : 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
Document type :
Book sections
Complete list of metadata

https://hal-univ-artois.archives-ouvertes.fr/hal-03301156
Contributor : Fabien Delorme <>
Submitted on : Tuesday, July 27, 2021 - 1:08:51 PM
Last modification on : Thursday, September 9, 2021 - 3:10:28 PM

Identifiers

  • HAL Id : hal-03301156, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

10