2009/10/14 by Chinmay Karande, Karande, Chinmay
Computer Science · Mathematics · #Algorithms and Data Compression #Combinatorics #Computational Complexity (cs.CC) #Computer science #FOS: Computer and information sciences #Knapsack problem #Mathematical optimization #Mathematics #cs.CC #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.0910.2649
arxiv created 2009/10/14 · openalex publication_date 2009/10/14 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
0-1 Knapsack is a fundamental NP-complete problem. In this article we prove that it remains NP-complete even when the weights of the objects in the packing constraints and their values in the objective function satisfy specific stringent conditions: the values are integral powers of the weights of the objects.