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 is the only assumption on the utilities , we show that, unless P=NP, no efficient polynomial factor approximation is possible. When additivity is relaxed to submodularity, we find that not even an exponential approximation is possible.