combinatorial allocation problems have been a subject of recent interest due to their role in on-line auctions and electronic commerce. an allocation problem entails a finite set of "items" that should be distributed among participating "players" in order to maximize a certain "social utility" function. a particular case of interest is the submodular welfare problem, where the utility functions are assumed to be submodular. our recent result is that a $(1-1/e)$-approximation can be achieved for the submodular welfare problem, which is known to be optimal. the $(1-1/e)$-approximation can be extended to a more general problem for which a $1/2$-approximation was known since 1978 [fisher,nemhauser,wolsey]. i will discuss our improvements and the techniques that we use - randomization, replacing the discrete problem by a continuous one, and approximately solving a non-linear optimization problem using a continuous greedy method. partly joint work with g. calinescu, c. chekuri and m. pal.