Partially-Ordered Knapsack and Applications to Scheduling

摘要

In the partially-ordered knapsack problem (POK) we are given a set N of items and a partial order <_p on N. Each item has a size and an associated weight. The objective is to pack a set N' is contained in N of maximum weight in a knapsack of bounded size. N' should be precedence-closed, i.e., be a valid prefix of <_p. POK is a natural generalization, for which very little is known, of the classical Knapsack problem. In this paper we advance the state-of-the-art for the problem through both positive and negative results. We give an FPTAS for the important case of a 2-dimensional partial order, a class of partial orders which is a substantial generalization of the series-parallel class, and we identify the first non-trivial special case for which a polynomial-time algorithm exists. We also characterize cases where the natural linear relaxation for POK is useful for approximation and we demonstrate its limitations. Our results have implications for approximation algorithms for scheduling precedence-constrained jobs on a single machine to minimize the sum of weighted completion times, a problem closely related to POK.