2015/08/29 by Hamza Alsarhan, Davin Chia, Alsarhan, Hamza +8
Computer Science · Engineering · #Advanced Manufacturing and Logistics Optimization #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Packing Problems #cs.DS #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1508.07380
arxiv created 2015/08/29 · openalex publication_date 2015/08/29 · arxiv updated 2015/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the Colored Bin Packing Problem: we are given a set of items where each item has a weight and color. We must pack the items in bins of uniform capacity such that no two items of the same color may be adjacent within in a bin. The goal is to perform this packing using the fewest number of bins. We consider a version of the problem where reordering is allowed. We first consider the zero-weight and unit weight versions of this problem, i.e. where the items have weight zero and one, respectively. We present linear time optimal algorithms for both versions.