We study a constrained version of the knapsack problem in which dependencies between items are given by the adjacencies of a graph. In the 1-neighbour knapsack problem, an item can be selected only if at least one of its neighbours is also selected. In the all-neighbours knapsack problem, an item can be selected only if all its neighbours are also selected. We give approximation algorithms and hardness results when the nodes have both uniform and arbitrary weight and profit functions, and when the dependency graph is directed and undirected.
In the subset-union knapsack problem (SUKP) @cite_9 , each item is a subset of a ground set of elements. Each element in the ground set has a weight and each item has a profit and the goal is to find a maximum-profit set of elements where the weight of the union of the elements in the sets fits in the knapsack. It is easy to see that this is a special case of the general, directed all-neighbours knapsack problem in which there is a vertex for each item and each element and an arc from an item to each element in the item's set. @cite_9 , Kellerer, Pferschy, and Pisinger show that SUKP is NP-hard and give an optimal but badly exponential algorithm. The precedence constrained knapsack problem @cite_0 and partially-ordered knapsack problem @cite_14 are special cases of the general, directed all-neighbours knapsack problem in which the dependency graph is a DAG. Hajiaghayi et. al. show that the partially-ordered knapsack problem is hard to approximate within a @math factor unless 3SAT @math DTIME @math @cite_5 .
@cite_0 @cite_5 @cite_9 @cite_14
2141422661 1975442866 2036199750
We consider a knapsack problem with precedence constraints imposed on pairs of items, known as the precedence constrained knapsack problem (PCKP). This problem has applications in manufacturing and mining, and also appears as a subproblem in decomposition techniques for network design and related problems. We present a new approach for determining facets of the PCKP polyhedron based on clique inequalities. A comparison with existing techniques, that lift knapsack cover inequalities for the PCKP, is also presented. It is shown that the clique-based approach generates facets that cannot be found through the existing cover-based approaches, and that the addition of clique-based inequalities for the PCKP can be computationally beneficial, for both PCKP instances arising in real applications, and applications in which PCKP appears as an embedded structure. Throughout the 1960s I worked on combinatorial optimization problems including logic circuit design with Paul Roth and assembly line balancing and the traveling salesman problem with Mike Held. These experiences made me aware that seemingly simple discrete optimization problems could hold the seeds of combinatorial explosions. The work of Dantzig, Fulkerson, Hoffman, Edmonds, Lawler and other pioneers on network flows, matching and matroids acquainted me with the elegant and efficient algorithms that were sometimes possible. Jack Edmonds’ papers and a few key discussions with him drew my attention to the crucial distinction between polynomial-time and superpolynomial-time solvability. I was also influenced by Jack’s emphasis on min-max theorems as a tool for fast verification of optimal solutions, which foreshadowed Steve Cook’s definition of the complexity class NP. Another influence was George Dantzig’s suggestion that integer programming could serve as a universal format for combinatorial optimization problems. 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.