5
$\begingroup$

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,

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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: icml-2011.org/papers/506_icmlpaper.pdf Thanks again, and it would be very useful if you can give me more information. $\endgroup$
    – Majid Yazdani
    Commented Apr 10, 2013 at 10:05
  • 2
    $\begingroup$ @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 theory.stanford.edu/~shaddin/papers/submodular_survey.pdf -- chasing some more refs. there might help. $\endgroup$
    – Suvrit
    Commented Apr 10, 2013 at 23:31

You must log in to answer this question.