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 pse...
保存先:
| 主要な著者: | , |
|---|---|
| フォーマット: | 論文 |
| 出版事項: |
2026
|
| 主題: | |
| オンライン･アクセス: | https://arxiv.org/abs/2609.17713 http://arxiv.org/abs/2609.17713 |
| タグ: |
タグなし, このレコードへの初めてのタグを付けませんか!
|