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 ...

Department dc:contributor.department

Massachusetts Institute of Technology. Operations Research Center.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2015

Author dc:creator

• Rhee, Donguk

Advisor dc:contributor.advisor

• James B. Orlin.

• Operations Research Center.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/98564

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/98564