A simple combinatorial algorithm for submodular function minimization
This paper presents a new simple algorithm for minimizing submodular functions. For integer valued submodular functions, the algorithm runs in O(n6EO log nM) [O (n superscript 6 E O log nM)] time, where n is the cardinality of the ground set, M is the maximum absolute value of the function value, an...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Society for Industrial and Applied Mathematics / Association for Computing Machinery
2011
|
| Online Access: | http://hdl.handle.net/1721.1/65187 https://orcid.org/0000-0002-7488-094X |
| _version_ | 1811068419105095680 |
|---|---|
| author | Iwata, Satoru Orlin, James B. |
| author2 | Sloan School of Management |
| author_facet | Sloan School of Management Iwata, Satoru Orlin, James B. |
| author_sort | Iwata, Satoru |
| collection | MIT |
| description | This paper presents a new simple algorithm for minimizing submodular functions. For integer valued submodular functions, the algorithm runs in O(n6EO log nM) [O (n superscript 6 E O log nM)] time, where n is the cardinality of the ground set, M is the maximum absolute value of the function value, and EO is the time for function evaluation. The algorithm can be improved to run in O ((n4EO+n5)log nM) [O ((n superscript 4 EO + n superscript 5) log nM)] time. The strongly polynomial version of this faster algorithm runs in O((n5EO + n6) log n) [O ((n superscript 5 EO + n superscript 6) log n)] time for real valued general submodular functions. These are comparable to the best known running time bounds for submodular function minimization. The algorithm can also be implemented in strongly polynomial time using only additions, subtractions, comparisons, and the oracle calls for function evaluation. This is the first fully combinatorial submodular function minimization algorithm that does not rely on the scaling method. |
| first_indexed | 2024-09-23T07:55:43Z |
| format | Article |
| id | mit-1721.1/65187 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T07:55:43Z |
| publishDate | 2011 |
| publisher | Society for Industrial and Applied Mathematics / Association for Computing Machinery |
| record_format | dspace |
| spelling | mit-1721.1/651872022-09-30T01:03:07Z A simple combinatorial algorithm for submodular function minimization Iwata, Satoru Orlin, James B. Sloan School of Management Orlin, James B. Orlin, James B. This paper presents a new simple algorithm for minimizing submodular functions. For integer valued submodular functions, the algorithm runs in O(n6EO log nM) [O (n superscript 6 E O log nM)] time, where n is the cardinality of the ground set, M is the maximum absolute value of the function value, and EO is the time for function evaluation. The algorithm can be improved to run in O ((n4EO+n5)log nM) [O ((n superscript 4 EO + n superscript 5) log nM)] time. The strongly polynomial version of this faster algorithm runs in O((n5EO + n6) log n) [O ((n superscript 5 EO + n superscript 6) log n)] time for real valued general submodular functions. These are comparable to the best known running time bounds for submodular function minimization. The algorithm can also be implemented in strongly polynomial time using only additions, subtractions, comparisons, and the oracle calls for function evaluation. This is the first fully combinatorial submodular function minimization algorithm that does not rely on the scaling method. United States. Office of Naval Research ( ONR grant N00014-08-1-0029) 2011-08-17T19:04:12Z 2011-08-17T19:04:12Z 2009-01 Article http://purl.org/eprint/type/ConferencePaper 1071-9040 http://hdl.handle.net/1721.1/65187 Iwata, Satoru and James B. Orlin. "A simple combinatorial algorithm for submodular function minimization" Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009) https://orcid.org/0000-0002-7488-094X en_US http://portal.acm.org/citation.cfm?id=1496903 ACM-SIAM Symposium on Discrete Algorithms (SODA)(20th, 2009) Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Society for Industrial and Applied Mathematics / Association for Computing Machinery MIT web domain |
| spellingShingle | Iwata, Satoru Orlin, James B. A simple combinatorial algorithm for submodular function minimization |
| title | A simple combinatorial algorithm for submodular function minimization |
| title_full | A simple combinatorial algorithm for submodular function minimization |
| title_fullStr | A simple combinatorial algorithm for submodular function minimization |
| title_full_unstemmed | A simple combinatorial algorithm for submodular function minimization |
| title_short | A simple combinatorial algorithm for submodular function minimization |
| title_sort | simple combinatorial algorithm for submodular function minimization |
| url | http://hdl.handle.net/1721.1/65187 https://orcid.org/0000-0002-7488-094X |
| work_keys_str_mv | AT iwatasatoru asimplecombinatorialalgorithmforsubmodularfunctionminimization AT orlinjamesb asimplecombinatorialalgorithmforsubmodularfunctionminimization AT iwatasatoru simplecombinatorialalgorithmforsubmodularfunctionminimization AT orlinjamesb simplecombinatorialalgorithmforsubmodularfunctionminimization |