A Simple Combinatorial Algorithm for Submodular Function Minimization
Published in Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms • Jan 4, 2009
NobleIDNI5P80W47R15S75
Authors:,
Satoru Iwata
James B. Orlin
Abstract
This paper presents a new simple algorithm for minimizing submodular functions. For integer valued submodular functions, the algorithm runs in O(n6EO log nM) time, where n is the cardinality of the ground set, M is the maximum absolute value of the function value, and EO is the time for function eva...
Finding related papers...
Discussions
(0)No comments yet
Be the first to share your thoughts!