Classes of submodular constraints expressible by graph cuts
Stanislav Živný and Peter G. Jeavons
Abstract
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.
Details
| Book Title |
Proceedings of the 14th International Conference on Principles and Practice of Constraint Programming (CP'08) |
| Pages |
112−127 |
| Series |
Lecture Notes in Computer Science |
| Volume |
5202 |
| Year |
2008 |
Links
DOI (10.1007/978-3-540-85958-1_8)
Related pages
|
People |
|
|
Activities |