ON THE PIPAGE ROUNDING ALGORITHM FORSUBMODULAR FUNCTION MAXIMIZATION — A VIEWFROM DISCRETE CONVEX ANALYSIS

摘要

We consider the problem of maximizing a nondecreasing submodular set functionunder a matroid constraint. Recently, Calinescu et al. (2007) proposed an elegant frame-work for the approximation of this problem, which is based on the pipage rounding tech-nique by Ageev and Sviridenko (2004), and showed that this framework indeed yieldsa (1 — 1/e)-approximation algorithm for the class of submodular functions which arerepresented as the sum of weighted rank functions of matroids. This paper sheds a newlight on this result from the viewpoint of discrete convex analysis by extending it to theclass of submodular functions which are the sum of NP-concave functions. Mil-concavefunctions are a class of discrete concave functions introduced by Murota and Shioura(1999), and contain the class of the sum of weighted rank functions as a proper sub-class. Our result provides a better understanding for why the pipage rounding algorithmworks for the sum of weighted rank functions. Based on the new observation, we furtherextend the approximation algorithm to the maximization of a nondecreasing submodularfunction over an integral polymatroid. This extension has an application in multi-unitcombinatorial auctions.