I have a real supermodular objective function which I want to maximize with constraint. The constraint is on the size, like |A|=k . 


I am wondering if anyone can give me more information about a practical solution applicable to a large set, particularly what we can say about the greedy algorithm?


Thanks in advance,



Maximizing supermodular functions
Maximizing a supermodular function is like minimizing a submodular function. This is a polynomial time activity, for which several algorithms are known (search google for **min norm algorithm** and you'll find many hits, including to a paper by Fujishige).


There are several other approaches available for solving submodular minimization. Do not confuse it with submodular maximization (or supermodular minimization), for which there are greedy algorithms --- because these problems are NP-Hard to approximate to a factor better than $1-1/e$ unless more structure is assumed. Again, google will find you many hits on the greedy algorithm for submodular maximization.


