Problems involving maximization of submodular functions arise in many applications, such as combinatorial auctions and coverage optimization in wireless networks. Submodular maximization can be also thought of as a unifying framefork for several classical problems including Max Cut, Max k-Cover and broadcast scheduling. The traditional approaches to maximization of submodular functions are combinatorial, using either greedy or local search techniques. I will describe a new approach, which is analogous to linear programming in the sense that a discrete problem is replaced by a continuous one. In the case of submodular functions, the objective function is replaced by a multilinear polynomial. This objective function is neither convex nor concave, and new techniques are required to handle it. Still, we show that this ‘‘multilinear relaxation’’ provides improved results for a wide range of problems and in several cases leads to an optimal approximation. A particular result I will discuss is an optimal (1-1/e)-approximation for welfare maximization in combinatorial auctions.