Multilinear relaxation: a tool for maximization of submodular functions
published: Jan. 13, 2011, recorded: December 2010, views: 402
Report a problem or upload filesIf you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
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.
Link this pageWould you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !