Report icon

Report

Generalising Submodularity and Horn Clauses: Tractable optimization problems defined by tournament pair multimorphisms

Abstract:
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 o... Expand abstract

Actions


Access Document


Files:

Authors


Peter Jeavons More by this author
Martin C Cooper More by this author
David A Cohen More by this author
Publisher:
Oxford University Computing Laboratory
Publication date:
2006-12-01
URN:
uuid:20aa2a6f-ef85-44d3-ba1d-763e9950428d
Local pid:
cs:51

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP