Publications of Tiziano Bacci

This page shows all publications that appeared in the IASI annual research reports. Authors currently affiliated with the Institute are always listed with the full name.

You can browse through them using either the links of the following line or those associated with author names.

Show all publications of the year  2018, with author Bacci T, in the category IASI Research Reports (or show them all):


IASI Research Report n. 18-03  (Previous    Next)  

Tiziano Bacci, Sara Nicoloso

A heuristic algorithm for the Bin Packing Problem with Conflicts on interval graphs

ABSTRACT
In this technical report 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.
back
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -