{"id":"arxiv/2602.12214","url":"https://arxiv.org/abs/2602.12214","tags":["math.OC"],"score":0,"title":"The colored knapsack problem: structural properties and exact algorithms","domain":"math.OC","source":"arxiv","authors":["Fabio Ciccarelli","Alexander Helber","Erik Mühmer"],"reviews":0,"subject":"math.OC","summary":"We introduce and study a novel generalization of the classical Knapsack Problem (KP), called the Colored Knapsack Problem (CKP). In this problem, the items are partitioned into classes of colors and the packed items need to be ordered such that no consecutive items are of the same color. We establish that the problem is weakly NP-hard and propose two exact dynamic programming algorithms with time complexities of $\\mathcal{O}(bn^4)$ and $\\mathcal{O}(b^2n^3)$, respectively. To enhance practical performance, we derive various dominance and fathoming rules for both approaches. From a theoretical…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-02-12","reactions":{}}