Tag
knapsack
- Aug 4, 2024 Pseudo-Polynomial Knapsack: Why the Capacity State Is Not Polynomial The O(nW) knapsack table is polynomial in the capacity value and exponential in its bit length, which is why the problem stays NP-hard and why scaling the weights yields an approximation scheme. algorithms
- May 27, 2024 Fractional Relaxation and the Knapsack Integrality Gap Why the density-ordered greedy rule is exactly optimal for fractional knapsack, how the 0/1 version loses a factor of two, and what value scaling buys back. algorithms