Report icon

Report

Which submodular functions are expressible using binary submodular functions?

Abstract:

Submodular functions occur in many combinatorial optimisation problems and a number of polynomial-time algorithms have been devised to minimise such functions. The time complexity of the fastest known general algorithm for submodular function minimisation (SFM) is O(n^6+n^5L), where n is the number of variables and L is the time required to evaluate the function.
However, many important special cases of SFM can be solved much more efficiently, and with much simpler algorithms. For examp...

Expand abstract

Actions


Authors


Publisher:
OUCL
Publication date:
2008-06-01
UUID:
uuid:3f6fc1ce-8175-423b-90d5-edd280f1797f
Local pid:
cs:85
Deposit date:
2015-03-31

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