arXiv preprint ·
A tight 1/3-approximation algorithm and fully polynomial-time approximation schemes for the Colored Knapsack Problem
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Learning Choice Model Trees for Feature-Based Multi-Product Pricing: Exact Optimization and Field Evidence
Matching Multi-Loop Complexities with a Single Loop: Optimal Optimization Stationarity and Best-Known Game Stationarity in Nonconvex--Concave Minimax Optimization
Optimization over covariance matrices with a parameterized metric
The Attention Within: Consensus Dynamics in Selective State Space Models
Intervention problems in the Linear Threshold Model: A general formulation and new results
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.