 In fact, when additivity is the only assumption on the utilities , we show that, unless P=NP, no polynomial time approximation is possible.
<meaning-changed>  In fact, when additivity is the only assumption on the utilities , we show that, unless P=NP, no polynomial time approximation is possible.
 In fact, when additivity and non-negativity are the only assumptions on the valuations , we show that, unless P=NP, no polynomial time approximation is possible.