Algorithms for Symmetric Submodular Function Minimization under Hereditary Constraints and Generalizations
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[superscript 3]) oracle calls to f and I, where n is the cardinality of the ground set. In contrast, the problem of minimizing a...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Society for Industrial and Applied Mathematics
2013
|
| Online Access: | http://hdl.handle.net/1721.1/80848 https://orcid.org/0000-0002-0520-1165 |
| _version_ | 1811087054987067392 |
|---|---|
| author | Goemans, Michel X. Soto, Jose A. |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Goemans, Michel X. Soto, Jose A. |
| author_sort | Goemans, Michel X. |
| collection | MIT |
| description | 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[superscript 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(√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[superscript 3]) oracle calls, and the second reports all extreme subsets of f using O(n[superscript 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[superscript 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. |
| first_indexed | 2024-09-23T13:39:04Z |
| format | Article |
| id | mit-1721.1/80848 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:39:04Z |
| publishDate | 2013 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | mit-1721.1/808482022-10-01T16:16:39Z Algorithms for Symmetric Submodular Function Minimization under Hereditary Constraints and Generalizations Goemans, Michel X. Soto, Jose A. Massachusetts Institute of Technology. Department of Mathematics Goemans, Michel X. 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[superscript 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(√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[superscript 3]) oracle calls, and the second reports all extreme subsets of f using O(n[superscript 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[superscript 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. National Science Foundation (U.S.) (Contract CCF-0829878) National Science Foundation (U.S.) (Contrac tCCF-1115849) United States. Office of Naval Research (Grant N00014-11-1-0053) 2013-09-23T12:47:04Z 2013-09-23T12:47:04Z 2013-06 2013-03 Article http://purl.org/eprint/type/JournalArticle 0895-4801 1095-7146 http://hdl.handle.net/1721.1/80848 Goemans, Michel X., and José A. Soto. “Algorithms for Symmetric Submodular Function Minimization under Hereditary Constraints and Generalizations.” SIAM Journal on Discrete Mathematics 27, no. 2 (April 4, 2013): 1123-1145. © 2013, Society for Industrial and Applied Mathematics https://orcid.org/0000-0002-0520-1165 en_US http://dx.doi.org/10.1137/120891502 SIAM Journal on Discrete Mathematics Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Society for Industrial and Applied Mathematics SIAM |
| spellingShingle | Goemans, Michel X. Soto, Jose A. Algorithms for Symmetric Submodular Function Minimization under Hereditary Constraints and Generalizations |
| title | Algorithms for Symmetric Submodular Function Minimization under Hereditary Constraints and Generalizations |
| title_full | Algorithms for Symmetric Submodular Function Minimization under Hereditary Constraints and Generalizations |
| title_fullStr | Algorithms for Symmetric Submodular Function Minimization under Hereditary Constraints and Generalizations |
| title_full_unstemmed | Algorithms for Symmetric Submodular Function Minimization under Hereditary Constraints and Generalizations |
| title_short | Algorithms for Symmetric Submodular Function Minimization under Hereditary Constraints and Generalizations |
| title_sort | algorithms for symmetric submodular function minimization under hereditary constraints and generalizations |
| url | http://hdl.handle.net/1721.1/80848 https://orcid.org/0000-0002-0520-1165 |
| work_keys_str_mv | AT goemansmichelx algorithmsforsymmetricsubmodularfunctionminimizationunderhereditaryconstraintsandgeneralizations AT sotojosea algorithmsforsymmetricsubmodularfunctionminimizationunderhereditaryconstraintsandgeneralizations |