Fabio Furini

A tight 1/3-approximation algorithm and fully polynomial-time approximation schemes for the Colored Knapsack Problem

The $\textit{Colored Knapsack Problem}$ (ColKP) generalizes the classical Knapsack Problem by partitioning the items into color classes and requiring the selected items to admit an ordering in which consecutive items have different colors. The problem is weakly $\mathcal{NP}$-hard and admits two pseudo-polynomial dynam...