Trying to find polynomial-time algorithms for knapsack-like problems Consider two related problems:


*

*You have $n$ cannisters that must go into $m$ trucks that can each carry $k$ cannisters. You require that no truck becomes overloaded, and for each cannister, there is a specified subset of trucks in which it may be safely carried. Is there a way to load all $n$ cannisters into the $m$ trucks such that no truck is overloaded, and each cannisters goes into a truck that is allowed to carry it?

*Now, any cannisters can be placed in any truck, but there are certain pairs of cannisters that cannot be placed together in the same truck. Is there a way to load all $n$ cannisters into the $m$ trucks such that no truck is overloaded, and no two cannisters are placed in the same truck when they're not supposed to be?


The question I have is whether either of these has a polynomial-time algorithm to solve it. When I think in terms of greedy algorithms, I can't really come up with anything, so is there a clever trick (or algorithm paradigm) that can be used to solve these in polynomial time?
 A: For question (1), yes, there is, using maximum matching / flow. Consider the bipartite graph $(L, R)$ -- each of the nodes $l_i$ in $L$ correspond to a canister, and each of the nodes $r_i$ in $R$ correspond to a truck. For every pair of allowed canister $(l_i, r_i)$, such that it is allowed to put canister $l_i$ inside truck $r_i$, construct an edge with capacity $1$ between them. Now, add two additional nodes $v_t$ and $v_s$. Add an edge from $v_t$ to every canister $l_i$, each with capacity $1$. Add an edge from every truck $r_i$ to $v_s$ with capacity $k$. A maximum flow in this graph corresponds to an assignment of canisters to trucks.
Question (2) is NP-hard, because Clique Cover can be reduced to this problem by setting $k=n$ and considers the complement graph.
A: Yes, there is a clever trick for approximating solutions to the knapsack problem. Since the knapsack problem is pseudo polynomial, we can find a full approximation scheme for it such that out approximation can be made arbitrarily close. The details are here:
http://math.mit.edu/~goemans/18434S06/knapsack-katherine.pdf
Basically, the trick is rounding your numbers.
