2017/07/03 by Tiziano Bacci, Bacci, Tiziano, Sara Nicoloso +1
Computer Science · Engineering · Mathematics · #Advanced Manufacturing and Logistics Optimization #Assembly Line Balancing Optimization #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Packing Problems #cs.DS #math.CO
paper · pdf · doi:10.48550/arxiv.1707.00496
openalex publication_date 2017/07/03 · arxiv created 2017/09/14 · arxiv updated 2017/09/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.