A heuristic algorithm for the Bin Packing Problem with Conflicts on Interval Graphs

arXiv1707.00496MaRDI QIDQ6288577FDOQ6288577

Publication date: 3 July 2017

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 nonnegative integer B, find a partition of the vertex set of the graph into k subsets such that the sum of the weights of the vertices assigned to same subset is less than or equal to B, two vertices connected by an edge do not belong to the same subset, and k is minimum. 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 existing algorithms.

This page was built for publication: A heuristic algorithm for the Bin Packing Problem with Conflicts on Interval Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6288577)