In this paper we deal with the Bin Packing Problem with Conflicts on interval graphs: given an interval graph, a nonnegative integer weight for each vertex, and a bound, find a partition of the vertex set of the graph into the minimum number of subsets such that the sum of the weights of the vertices assigned to the same subset does not exceed the bound and two vertices connected by an edge do not belong to the same subset. We design a heuristic algorithm and propose a new random interval graph generator which builds interval conflict graphs with desired edge density. We test the algorithm on a huge test bed and compare the results with the best heuristic algorithms: the experiments show that our method outperform the other ones when the average number of vertices per subset is greater than or equal to three.
A heuristic algorithm for the Bin Packing Problem with Conflicts on interval graphs
Tiziano Bacci;Sara Nicoloso
2018
Abstract
In this paper we deal with the Bin Packing Problem with Conflicts on interval graphs: given an interval graph, a nonnegative integer weight for each vertex, and a bound, find a partition of the vertex set of the graph into the minimum number of subsets such that the sum of the weights of the vertices assigned to the same subset does not exceed the bound and two vertices connected by an edge do not belong to the same subset. We design a heuristic algorithm and propose a new random interval graph generator which builds interval conflict graphs with desired edge density. We test the algorithm on a huge test bed and compare the results with the best heuristic algorithms: the experiments show that our method outperform the other ones when the average number of vertices per subset is greater than or equal to three.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.