Back to search

Clemson University

A PTAS for the Uncertain Capacity Knapsack Problem

Abstract

dc:description.abstract

The standard NP-hard knapsack problem can be interpreted as a scheduling problem with n jobs with weights w1 . . .wn and processing times p1 . . . pn, 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.

Degree

thesis:*
Name thesis:degree_name
Master of Science (MS)
Level thesis:degree_level
Thesis

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Dabney, Matthew
Contributors dc:contributor
  • Dean, Brian C
  • Hallstrom , Jason O
  • Jacobs , David P

Subjects

dc:subject × 6

Identifiers

dc:identifier.*
Repository record dc:identifier
https://open.clemson.edu/all_theses/982

Chain of custody

source
Harvested from
Clemson University
Base URL
open.clemson.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Dabney, Matthew. A PTAS for the Uncertain Capacity Knapsack Problem. Thesis thesis, https://open.clemson.edu/all_theses/982