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^′⊆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 present both positive and negative results. We give an FPTAS for the important case of a two-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. 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.