Journal article icon

Journal article

Generalising submodularity and horn clauses: Tractable optimization problems defined by tournament pair multimorphismsa

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 of SFM is ...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Publisher Version

Actions


Access Document


Files:
Publisher copy:
10.1016/j.tcs.2008.03.015

Authors


More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Computer Science
Role:
Author
Publisher:
Elsevier B.V. Publisher's website
Journal:
THEORETICAL COMPUTER SCIENCE Journal website
Volume:
401
Issue:
1-3
Pages:
36-51
Publication date:
2008-07-23
DOI:
ISSN:
0304-3975
URN:
uuid:a8286e66-e31e-445a-8e63-4301d27d17ad
Source identifiers:
291155
Local pid:
pubs:291155

Terms of use


Metrics


Views and Downloads






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

TO TOP