Submodular-function maximization is a central problem in combinatorial optimization, generalizing many important NP-hard problems including Max Cut in digraphs, graphs and hypergraphs, certain constraint satisfaction problems, maximum-entropy sampling, and maximum facility-location problems. Our main result is that for any k ≥ 2 and any ε > 0, there is a natural local-search algorithm which has approximation guarantee of 1/(k + ε) for the problem of maximizing a monotone submodular function subject to k matroid constraints. This improves a 1/(k + 1)-approximation of Nemhauser, Wolsey and Fisher, obtained more than 30 years ago. Also, our analysis can be applied to the problem of maximizing a linear objective function and even a general non-monotone submodular function subject to k matroid constraints. We shown that in these cases the approximation guarantees of our algorithms are 1/(k − 1 + ε) and 1/(k + 1 + 1/k + ε), respectively.
By: Jon Lee; Maxim Sviridenko; Jan Vondrák
Published in: RC24775 in 2009
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .