Generalising submodularity and Horn clauses: tractable optimization problems defined by tournament pair multimorphisms
The submodular function minimization problem (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...
| Egile Nagusiak: | , , |
|---|---|
| Formatua: | Journal article |
| Argitaratua: |
2008
|
| _version_ | 1826298514948227072 |
|---|---|
| author | Cohen, D Cooper, M Jeavons, P |
| author_facet | Cohen, D Cooper, M Jeavons, P |
| author_sort | Cohen, D |
| collection | OXFORD |
| description | The submodular function minimization problem (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 tournament pair multimorphism. 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-07T04:48:02Z |
| format | Journal article |
| id | oxford-uuid:d3fc1a4d-d193-4057-a1e5-eb28e293bb44 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T04:48:02Z |
| publishDate | 2008 |
| record_format | dspace |
| spelling | oxford-uuid:d3fc1a4d-d193-4057-a1e5-eb28e293bb442022-03-27T08:15:06ZGeneralising submodularity and Horn clauses: tractable optimization problems defined by tournament pair multimorphismsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:d3fc1a4d-d193-4057-a1e5-eb28e293bb44Department of Computer Science2008Cohen, DCooper, MJeavons, PThe submodular function minimization problem (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 tournament pair multimorphism. 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 | Cohen, D Cooper, M Jeavons, P 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 cohend generalisingsubmodularityandhornclausestractableoptimizationproblemsdefinedbytournamentpairmultimorphisms AT cooperm generalisingsubmodularityandhornclausestractableoptimizationproblemsdefinedbytournamentpairmultimorphisms AT jeavonsp generalisingsubmodularityandhornclausestractableoptimizationproblemsdefinedbytournamentpairmultimorphisms |