Generalising Submodularity and Horn Clauses: Tractable optimization problems defined by tournament pair multimorphisms
<em>The submodular function minimization problem</em> (SFM) is a fundamental problem in combinatorial optimization and several fully combinatorial polynomial-time algorithms have recently been discovered to solve this problem. The most general versions of these algorithms are able to min...
| Hlavní autoři: | , , |
|---|---|
| Médium: | Report |
| Vydáno: |
Oxford University Computing Laboratory
2006
|
| _version_ | 1826262750293131264 |
|---|---|
| author | Jeavons, P Cooper, M Cohen, D |
| author_facet | Jeavons, P Cooper, M Cohen, D |
| author_sort | Jeavons, P |
| collection | OXFORD |
| description | <em>The submodular function minimization problem</em> (SFM) is a fundamental problem in combinatorial optimization and several fully combinatorial polynomial-time algorithms have recently been discovered to solve this problem. The most general versions of these algorithms are able to minimize any submodular function whose domain is a set of tuples over any totally-ordered finite set and whose range includes both finite and infinite values. In this paper we demonstrate that this general form of SFM is just one example of a much larger class of tractable discrete optimization problems defined by valued constraints. These tractable problems are characterized by the fact that their valued constraints have an algebraic property which we call a<em>tournament pair multimorphism.</em> This larger tractable class also includes the problem of satisfying a set of Horn clauses (Horn-SAT), as well as various extensions of this problem to larger finite domains. |
| first_indexed | 2024-03-06T19:41:00Z |
| format | Report |
| id | oxford-uuid:20aa2a6f-ef85-44d3-ba1d-763e9950428d |
| institution | University of Oxford |
| last_indexed | 2024-03-06T19:41:00Z |
| publishDate | 2006 |
| publisher | Oxford University Computing Laboratory |
| record_format | dspace |
| spelling | oxford-uuid:20aa2a6f-ef85-44d3-ba1d-763e9950428d2022-03-26T11:28:49ZGeneralising Submodularity and Horn Clauses: Tractable optimization problems defined by tournament pair multimorphismsReporthttp://purl.org/coar/resource_type/c_93fcuuid:20aa2a6f-ef85-44d3-ba1d-763e9950428dDepartment of Computer ScienceOxford University Computing Laboratory2006Jeavons, PCooper, MCohen, D<em>The submodular function minimization problem</em> (SFM) is a fundamental problem in combinatorial optimization and several fully combinatorial polynomial-time algorithms have recently been discovered to solve this problem. The most general versions of these algorithms are able to minimize any submodular function whose domain is a set of tuples over any totally-ordered finite set and whose range includes both finite and infinite values. In this paper we demonstrate that this general form of SFM is just one example of a much larger class of tractable discrete optimization problems defined by valued constraints. These tractable problems are characterized by the fact that their valued constraints have an algebraic property which we call a<em>tournament pair multimorphism.</em> This larger tractable class also includes the problem of satisfying a set of Horn clauses (Horn-SAT), as well as various extensions of this problem to larger finite domains. |
| spellingShingle | Jeavons, P Cooper, M Cohen, D Generalising Submodularity and Horn Clauses: Tractable optimization problems defined by tournament pair multimorphisms |
| title | Generalising Submodularity and Horn Clauses: Tractable optimization problems defined by tournament pair multimorphisms |
| title_full | Generalising Submodularity and Horn Clauses: Tractable optimization problems defined by tournament pair multimorphisms |
| title_fullStr | Generalising Submodularity and Horn Clauses: Tractable optimization problems defined by tournament pair multimorphisms |
| title_full_unstemmed | Generalising Submodularity and Horn Clauses: Tractable optimization problems defined by tournament pair multimorphisms |
| title_short | Generalising Submodularity and Horn Clauses: Tractable optimization problems defined by tournament pair multimorphisms |
| title_sort | generalising submodularity and horn clauses tractable optimization problems defined by tournament pair multimorphisms |
| work_keys_str_mv | AT jeavonsp generalisingsubmodularityandhornclausestractableoptimizationproblemsdefinedbytournamentpairmultimorphisms AT cooperm generalisingsubmodularityandhornclausestractableoptimizationproblemsdefinedbytournamentpairmultimorphisms AT cohend generalisingsubmodularityandhornclausestractableoptimizationproblemsdefinedbytournamentpairmultimorphisms |