Multilinear relaxation: a tool for maximization of submodular functions

author: Jan Vondrak, IBM Almaden Research Center, IBM Research
published: Jan. 13, 2011,   recorded: December 2010,   views: 4783


Related Open Educational Resources

Related content

Report a problem or upload files

If 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.
Lecture popularity: You need to login to cast your vote.


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.

See Also:

Download slides icon Download slides: nipsworkshops2010_vondrak_mlr_01.pdf (559.5 KB)

Help icon Streaming Video Help

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: