
doi: 10.1137/120891502
handle: 10533/148233 , 1721.1/80848
We present an efficient algorithm to find nonempty minimizers of a symmetric submodular function $f$ over any family of sets ${\cal I}$ closed under inclusion. Our algorithm makes $O(n^3)$ oracle calls to $f$ and ${\cal I}$, where $n$ is the cardinality of the ground set. In contrast, the problem of minimizing a general submodular function under a cardinality constraint is known to be inapproximable within $o(\sqrt{n/\log n})$ [Z. Svitkina and L. Fleischer, in Proceedings of the $49$th Annual IEEE Symposium on Foundations of Computer Science, IEEE, Washington, DC, 2008, pp. 697--706]. We also present two extensions of the above algorithm. The first extension reports all nontrivial inclusionwise minimal minimizers of $f$ over ${\cal I}$ using $O(n^3)$ oracle calls, and the second reports all extreme subsets of $f$ using $O(n^4)$ oracle calls. Our algorithms are similar to a procedure by Nagamochi and Ibaraki [Inform. Process. Lett., 67 (1998), pp. 239--244] that finds all nontrivial inclusionwise minimal m...
submodular functions
submodular functions
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 3 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
