Approximation and scaling algorithms improve colored knapsack solutions
A tight 1/3-approximation algorithm and fully polynomial-time approximation schemes for the Colored Knapsack Problem
Data Structures and Algorithms
Summary
The Colored Knapsack Problem is a tricky puzzle where you must pick items of different colors so no two neighboring items share the same color, while fitting them into a limited space to maximize value. The authors designed the first fast method that can quickly find a good set of items, guaranteeing it will be at least a third as good as the best possible. They also created more advanced techniques that come very close to the best solution and run efficiently even for large problems. These methods help understand how to handle the color restriction in useful ways.
What this means in practice
- •For software engineers: Design algorithms for resource allocation where tasks or resources must alternate distinctive categories to meet practical constraints.
- •For logistics planners: Plan shipments or cargo loading that require avoiding consecutive similar container types while maximizing value within capacity limits.
Authors
Fabio Ciccarelli, Fabio Furini
Abstract
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 dynamic programming (DP) algorithms proposed in the literature. These two DP algorithms have worst-case running times $O(b \, n^4)$ and $O(b^2 \, n^3)$, respectively, where $b$ is the knapsack capacity and $n$ is the number of items. We develop the first approximation algorithm for the ColKP. By rounding an optimal basic solution of the linear programming relaxation of its natural integer programming formulation and repairing color feasibility, we obtain a linear-time approximation-algorithm whose worst-case performance ratio is $1/3$. We then reformulate both DP algorithms so that profit, rather than knapsack capacity, indexes their pseudo-polynomial dimension, and combine them with profit scaling to obtain two fully polynomial-time approximation schemes (FPTASs). The first FPTAS runs in $O(n^5/\varepsilon)$ time for nonnegative profits and in $O(n^6/\varepsilon)$ time for arbitrary integer profits. The second FPTAS runs instead in $O(n^5/\varepsilon^2)$ and $O(n^7/\varepsilon^2)$ time, respectively. The approximation guarantee, along with new structural insights, provides the bounds needed to control the scaled profit range and establish these running times.