Timeline for Maximizing supermodular functions
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 10, 2013 at 23:31 | comment | added | Suvrit | @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. | |
| Apr 10, 2013 at 10:05 | comment | added | Majid Yazdani | 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. | |
| Apr 9, 2013 at 15:21 | vote | accept | Majid Yazdani | ||
| Apr 9, 2013 at 15:03 | history | answered | Suvrit | CC BY-SA 3.0 |