Journal article icon

Journal article

Efficient minimization of higher order submodular functions using monotonic Boolean functions

Abstract:

Submodular function minimization is a key problem in a wide variety of applications in machine learning, economics, game theory, computer vision, and many others. The general solver has a complexity of O(n3 log2 n:E + n4logO(1)n) where E is the time required to evaluate the function and n is the number of variables [32]. On the other hand, many computer vision and machine learning problems are defined over special subclasses of submodular functions that can be written as the sum of many su...

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

Actions


Access Document


Files:
Publisher copy:
10.1016/j.dam.2016.11.022

Authors


More by this author
Role:
Author
ORCID:
0000-0002-2598-0151
More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Engineering Science
Role:
Author
More from this funder
Grant:
ERC-2012-AdG 321162-HELIOS
Max Planck Center for Learning Systems Fellowship More from this funder
Mitsubishi Electric Research Laboratories More from this funder
Publisher:
Elsevier Publisher's website
Journal:
Discrete Applied Mathematics Journal website
Volume:
220
Pages:
1-19
Publication date:
2017-01-01
Acceptance date:
2016-11-25
DOI:
ISSN:
0166-218X
Source identifiers:
812230
Keywords:
Pubs id:
pubs:812230
UUID:
uuid:6f5354a2-3752-4602-b344-7095f36f0c80
Local pid:
pubs:812230
Deposit date:
2017-12-21

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