2015/11/15 by Hamza Alsarhan, Davin Chia, Alsarhan, Hamza +7
Computer Science · Engineering · #Advanced Manufacturing and Logistics Optimization #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Manufacturing Process and Optimization #Optimization and Packing Problems #cs.DS
paper · pdf · doi:10.48550/arxiv.1511.04762
arxiv created 2015/11/15 · openalex publication_date 2015/11/15 · arxiv updated 2015/11/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the Colored Bin Packing problem a set of items with varying weights and colors must be packed into bins of uniform weight limit such that no two items of the same color may be packed adjacently within a bin. We solve this problem for the case where there are two or more colors when the items have zero weight and when the items have unit weight. Our algorithms are optimal and run in linear time. Since our algorithms apply for two or more colors, they demonstrate that the problem does not get harder as the number of colors increases. We also provide closed-form expressions for the optimal number of bins.