Which submodular functions are expressible using binary submodular functions?
Submodular functions occur in many combinatorial optimisation problems and a number of polynomial-time algorithms have been devised to minimise such functions. The time complexity of the fastest known general algorithm for submodular function minimisation (SFM) is O(n^6+n^5L), where n is the number...
| Main Authors: | , |
|---|---|
| Format: | Report |
| Published: |
OUCL
2008
|
| _version_ | 1797064477310451712 |
|---|---|
| author | Živný, S Jeavons, P |
| author_facet | Živný, S Jeavons, P |
| author_sort | Živný, S |
| collection | OXFORD |
| description | Submodular functions occur in many combinatorial optimisation problems and a number of polynomial-time algorithms have been devised to minimise such functions. The time complexity of the fastest known general algorithm for submodular function minimisation (SFM) is O(n^6+n^5L), where n is the number of variables and L is the time required to evaluate the function. <br/> However, many important special cases of SFM can be solved much more efficiently, and with much simpler algorithms. For example, the (s,t)-Min-Cut problem is a special case of SFM which can be solved in cubic time. Moreover, any submodular function which can be expressed as a sum of binary submodular functions can be minimised by computing a minimal cut in a suitable graph. It has been known for some time that all ternary submodular functions are expressible in this way, by introducing additional variables. We have recently identified, for each k>=4, a subclass of k-ary submodular functions which are also expressible in this way. <br/> It was previously an open question whether all submodular functions could be expressed as a sum of binary submodular functions over a larger set of variables: in this paper we show that they cannot. Moreover, we characterise precisely which 4-ary submodular functions can be expressed in this way. This result can also be seen as characterising which pseudo-Boolean functions of degree 4 can be expressed as projections of quadratic submodular functions. <br/> Our results provide a more efficient algorithm for certain discrete optimisation problems which can be formulated as valued constraint satisfaction problems (VCSP). We define a new maximal class of VCSP instances with submodular constraints which are expressible using binary submodular functions with a bounded number of additional variables. It follows that optimal solutions to such instances can be computed in O((n+k)^3) time, where n is the number of variables and k is the number of higher-order (non-binary) constraints, by a straightforward reduction to the (s,t)-Min-Cut problem. |
| first_indexed | 2024-03-06T21:14:53Z |
| format | Report |
| id | oxford-uuid:3f6fc1ce-8175-423b-90d5-edd280f1797f |
| institution | University of Oxford |
| last_indexed | 2024-03-06T21:14:53Z |
| publishDate | 2008 |
| publisher | OUCL |
| record_format | dspace |
| spelling | oxford-uuid:3f6fc1ce-8175-423b-90d5-edd280f1797f2022-03-26T14:31:59ZWhich submodular functions are expressible using binary submodular functions?Reporthttp://purl.org/coar/resource_type/c_93fcuuid:3f6fc1ce-8175-423b-90d5-edd280f1797fDepartment of Computer ScienceOUCL2008Živný, SJeavons, PSubmodular functions occur in many combinatorial optimisation problems and a number of polynomial-time algorithms have been devised to minimise such functions. The time complexity of the fastest known general algorithm for submodular function minimisation (SFM) is O(n^6+n^5L), where n is the number of variables and L is the time required to evaluate the function. <br/> However, many important special cases of SFM can be solved much more efficiently, and with much simpler algorithms. For example, the (s,t)-Min-Cut problem is a special case of SFM which can be solved in cubic time. Moreover, any submodular function which can be expressed as a sum of binary submodular functions can be minimised by computing a minimal cut in a suitable graph. It has been known for some time that all ternary submodular functions are expressible in this way, by introducing additional variables. We have recently identified, for each k>=4, a subclass of k-ary submodular functions which are also expressible in this way. <br/> It was previously an open question whether all submodular functions could be expressed as a sum of binary submodular functions over a larger set of variables: in this paper we show that they cannot. Moreover, we characterise precisely which 4-ary submodular functions can be expressed in this way. This result can also be seen as characterising which pseudo-Boolean functions of degree 4 can be expressed as projections of quadratic submodular functions. <br/> Our results provide a more efficient algorithm for certain discrete optimisation problems which can be formulated as valued constraint satisfaction problems (VCSP). We define a new maximal class of VCSP instances with submodular constraints which are expressible using binary submodular functions with a bounded number of additional variables. It follows that optimal solutions to such instances can be computed in O((n+k)^3) time, where n is the number of variables and k is the number of higher-order (non-binary) constraints, by a straightforward reduction to the (s,t)-Min-Cut problem. |
| spellingShingle | Živný, S Jeavons, P Which submodular functions are expressible using binary submodular functions? |
| title | Which submodular functions are expressible using binary submodular functions? |
| title_full | Which submodular functions are expressible using binary submodular functions? |
| title_fullStr | Which submodular functions are expressible using binary submodular functions? |
| title_full_unstemmed | Which submodular functions are expressible using binary submodular functions? |
| title_short | Which submodular functions are expressible using binary submodular functions? |
| title_sort | which submodular functions are expressible using binary submodular functions |
| work_keys_str_mv | AT zivnys whichsubmodularfunctionsareexpressibleusingbinarysubmodularfunctions AT jeavonsp whichsubmodularfunctionsareexpressibleusingbinarysubmodularfunctions |