Algorithms for symmetric submodular function minimization under hereditary constraints and generalizations
Author
dc.contributor.author
Soto San Martín, José
Admission date
dc.date.accessioned
2014-01-27T19:45:33Z
Available date
dc.date.available
2014-01-27T19:45:33Z
Publication date
dc.date.issued
2013
Cita de ítem
dc.identifier.citation
Discrete Math, Vol. 27, No. 2, pp. 1123–1145
en_US
Identifier
dc.identifier.other
doi: 10.1137/120891502
Identifier
dc.identifier.uri
https://repositorio.uchile.cl/handle/2250/126292
General note
dc.description
Artículo de publicación ISI.
en_US
Abstract
dc.description.abstract
We present an efficient algorithm to find nonempty minimizers of a symmetric submodular function f over any family of sets I closed under inclusion. Our algorithm makes O(n(3)) oracle calls to f and 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(root n/log n) [Z. Svitkina and L. Fleischer, in Proceedings of the 49th 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 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 minimizers of a symmetric submodular function over a set of size n using O(n(3)) oracle calls. Their procedure in turn is based on Queyranne's algorithm [M. Queyranne, Math. Program., 82 (1998), pp. 3-12] to minimize a symmetric submodular function by finding pendent pairs. Our results extend to any class of functions for which we can find a pendent pair whose head is not a given element.
en_US
Patrocinador
dc.description.sponsorship
NSF contracts
CCF-0829878 and CCF-1115849 and by ONR grant N00014-11-1-0053.N´ucleo Milenio Informaci´on y
Coordinaci´on en Redes ICM/FIC P10-024F