MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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,

share|cite|improve this question
up vote 0 down vote accepted

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.

share|cite|improve this answer
Your hint was very useful. If I understand correctly, when constraint is added, lets say I want to find first K element -- |A|=K --, then the problem is not polynomial any more. Moreover, I am dealing with a large number of elements (> 500K) and not only being polynomial can be useful. I am continuing with: Thanks again, and it would be very useful if you can give me more information. – Majid Yazdani Apr 10 '13 at 10:05
@Majid: size constrained submodular minimization is hard; you found one of the papers there. Given the problem size you have, you might benefit from heuristics or approximation algorithms. Have a look at pg. 15 of this short report -- chasing some more refs. there might help. – Suvrit Apr 10 '13 at 23:31

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.