Journal article icon

Journal article

The Expressive Power of Binary Submodular Functions

Abstract:

We investigate whether all Boolean submodular functions can be decomposed into a sum of binary submodular functions over a possibly larger set of variables. This question has been considered within several different contexts in computer science, including computer vision, artificial intelligence, and pseudo-Boolean optimisation. Using a connection between the expressive power of valued constraints and certain algebraic properties of functions, we answer this question negatively. Our results h...

Expand abstract

Actions


Access Document


Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
Journal:
CoRR More from this journal
Volume:
abs/0811.1885
Pages:
744-757
Publication date:
2008-01-01
DOI:
EISSN:
1611-3349
ISSN:
0302-9743
Language:
English
Keywords:
Pubs id:
pubs:296307
UUID:
uuid:d4deea3a-0e72-4291-a3fe-c844cce5126c
Local pid:
pubs:296307
Source identifiers:
296307
Deposit date:
2013-02-20

Terms of use


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