Faster fully polynomial approximation schemes for Knapsack problems
Thesis: S.M., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2015.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2015
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/98564 |
| _version_ | 1811082504448245760 |
|---|---|
| author | Rhee, Donguk |
| author2 | James B. Orlin. |
| author_facet | James B. Orlin. Rhee, Donguk |
| author_sort | Rhee, Donguk |
| collection | MIT |
| description | Thesis: S.M., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2015. |
| first_indexed | 2024-09-23T12:04:28Z |
| format | Thesis |
| id | mit-1721.1/98564 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T12:04:28Z |
| publishDate | 2015 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/985642019-04-10T11:09:58Z Faster fully polynomial approximation schemes for Knapsack problems Faster FPTASs for Knapsack problems Rhee, Donguk James B. Orlin. Massachusetts Institute of Technology. Operations Research Center. Massachusetts Institute of Technology. Operations Research Center. Operations Research Center. Thesis: S.M., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2015. This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. Cataloged from student-submitted PDF version of thesis. Includes bibliographical references (pages 61-62). 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 ... by Donguk Rhee. S.M. 2015-09-17T17:42:51Z 2015-09-17T17:42:51Z 2015 2015 Thesis http://hdl.handle.net/1721.1/98564 920857251 eng 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. http://dspace.mit.edu/handle/1721.1/7582 62 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Operations Research Center. Rhee, Donguk Faster fully polynomial approximation schemes for Knapsack problems |
| title | Faster fully polynomial approximation schemes for Knapsack problems |
| title_full | Faster fully polynomial approximation schemes for Knapsack problems |
| title_fullStr | Faster fully polynomial approximation schemes for Knapsack problems |
| title_full_unstemmed | Faster fully polynomial approximation schemes for Knapsack problems |
| title_short | Faster fully polynomial approximation schemes for Knapsack problems |
| title_sort | faster fully polynomial approximation schemes for knapsack problems |
| topic | Operations Research Center. |
| url | http://hdl.handle.net/1721.1/98564 |
| work_keys_str_mv | AT rheedonguk fasterfullypolynomialapproximationschemesforknapsackproblems AT rheedonguk fasterfptassforknapsackproblems |