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
Version:
Accepted manuscript

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
Max Planck Center for Learning Systems Fellowship More from this funder
More from this funder
Grant:
ERC-2012-AdG 321162-HELIOS
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-05
Acceptance date:
2016-11-25
DOI:
ISSN:
0166-218X
Pubs id:
pubs:812230
URN:
uri:6f5354a2-3752-4602-b344-7095f36f0c80
UUID:
uuid:6f5354a2-3752-4602-b344-7095f36f0c80
Local pid:
pubs:812230

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