Classes of submodular constraints expressible by graph cuts
Submodular constraints play an important role both in theory and practice of valued constraint satisfaction problems (VCSPs). It has previously been shown, using results from the theory of combinatorial optimisation, that instances of VCSPs with submodular constraints can be minimised in polynomial...
| المؤلفون الرئيسيون: | , |
|---|---|
| التنسيق: | Conference item |
| منشور في: |
2008
|
| _version_ | 1826281558824189952 |
|---|---|
| author | Živný, S Jeavons, P |
| author_facet | Živný, S Jeavons, P |
| author_sort | Živný, S |
| collection | OXFORD |
| description | Submodular constraints play an important role both in theory and practice of valued constraint satisfaction problems (VCSPs). It has previously been shown, using results from the theory of combinatorial optimisation, that instances of VCSPs with submodular constraints can be minimised in polynomial time. However, the general algorithm is of order O(n^6) and hence rather impractical. In this paper, by using results from the theory of pseudo-Boolean optimisation, we identify several broad classes of submodular constraints over a Boolean domain which are expressible using binary submodular constraints, and hence can be minimised in cubic time. We also discuss the question of whether all submodular constraints of bounded arity over a Boolean domain are expressible using only binary submodular constraints, and can therefore be minimised efficiently. |
| first_indexed | 2024-03-07T00:30:37Z |
| format | Conference item |
| id | oxford-uuid:7fa94a8c-7819-4a3e-aa39-ca4731df153f |
| institution | University of Oxford |
| last_indexed | 2024-03-07T00:30:37Z |
| publishDate | 2008 |
| record_format | dspace |
| spelling | oxford-uuid:7fa94a8c-7819-4a3e-aa39-ca4731df153f2022-03-26T21:18:17ZClasses of submodular constraints expressible by graph cutsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:7fa94a8c-7819-4a3e-aa39-ca4731df153fDepartment of Computer Science2008Živný, SJeavons, PSubmodular constraints play an important role both in theory and practice of valued constraint satisfaction problems (VCSPs). It has previously been shown, using results from the theory of combinatorial optimisation, that instances of VCSPs with submodular constraints can be minimised in polynomial time. However, the general algorithm is of order O(n^6) and hence rather impractical. In this paper, by using results from the theory of pseudo-Boolean optimisation, we identify several broad classes of submodular constraints over a Boolean domain which are expressible using binary submodular constraints, and hence can be minimised in cubic time. We also discuss the question of whether all submodular constraints of bounded arity over a Boolean domain are expressible using only binary submodular constraints, and can therefore be minimised efficiently. |
| spellingShingle | Živný, S Jeavons, P Classes of submodular constraints expressible by graph cuts |
| title | Classes of submodular constraints expressible by graph cuts |
| title_full | Classes of submodular constraints expressible by graph cuts |
| title_fullStr | Classes of submodular constraints expressible by graph cuts |
| title_full_unstemmed | Classes of submodular constraints expressible by graph cuts |
| title_short | Classes of submodular constraints expressible by graph cuts |
| title_sort | classes of submodular constraints expressible by graph cuts |
| work_keys_str_mv | AT zivnys classesofsubmodularconstraintsexpressiblebygraphcuts AT jeavonsp classesofsubmodularconstraintsexpressiblebygraphcuts |