A PTAS for the Uncertain Capacity Knapsack Problem

Author

Matthew Dabney, Clemson UniversityFollow

Date of Award

12-2010

Document Type

Thesis

Degree Name

Master of Science (MS)

Committee Chair/Advisor

Dean, Brian C

Committee Member

Hallstrom , Jason O

Committee Member

Jacobs , David P

Abstract

The standard NP-hard knapsack problem can be interpreted as a scheduling problem with n jobs with weights w₁ . . .w_n and processing times p₁ . . . p_n, where our goal is to order the jobs on a single machine so as to maximize the weight of all jobs completing prior to a known common deadline d. In this paper, we study the uncertain capacity knapsack problem (UCKP), a generalization of this problem in which the deadline d is not known with certainty, but rather is provided as a probability distribution, and our goal is to order the jobs so as to maximize the expected weight of the set of jobs completing by the deadline. We develop a polynomial-time approximation scheme (PTAS) for this problem. We make no assumptions about probability distributions except that each job, scheduled by itself, completes by the deadline with some constant probability.

Recommended Citation

Dabney, Matthew, "A PTAS for the Uncertain Capacity Knapsack Problem" (2010). All Theses. 982.
https://tigerprints.clemson.edu/all_theses/982