Which submodular functions are expressible using binary submodular functions?
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.Expand abstract
However, many important special cases of SFM can be solved much more efficiently, and with much simpler algorithms. For examp...
- Publication date:
- Local pid:
- Deposit date:
- Copyright date:
If you are the owner of this record, you can report an update to it here: Report update to this record