Faster fully polynomial approximation schemes for Knapsack problems

[摘要] A fully polynomial time approximation scheme (FPTAS) is an algorithm that returns ... -optimal solution to a maximization problem of size n, which runs in polynomial time in both ... We develop faster FPTASs for several classes of knapsack problems. In this thesis, we will first survey the relevant literature in FPTASs for knapsack problems. We propose the use of floating point arithmetic rather than the use of geometric rounding in order to simplify analysis. Given a knapsack problem that yield an ... -optimal solution for disjoint subsets S and T of decision variables, we show how to attain ... -optimal solution for the knapsack problem for the set ... We use this procedure to speed up the run-time of FPTASs for: 1. The Integer Knapsack Problem, 2. The Unbounded Integer Knapsack Problem, 3. The Multiple-Choice Knapsack Problem, and, 4. The Nonlinear Integer Knapsack Problem, Using addition ideas, we develop a fast fully polynomial time randomized approximation scheme (FPTAS) for the 0-1 Knapsack Problem, which has the run-time of ...

[发布机构] Massachusetts Institute of Technology