Before revision:  In fact, when additivity is the only assumption on the utilities , we show that, unless P=NP, no polynomial time approximation is possible.
After revision:  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.