On submodular function minimization |
| |
Authors: | William H Cunningham |
| |
Institution: | (1) Department of Mathematics and Statistics, Carleton University, K1S 5B6 Ottawa, Canada |
| |
Abstract: | Earlier work of Bixby, Cunningham, and Topkis is extended to give a combinatorial algorithm for the problem of minimizing
a submodular function, for which the amount of work is bounded by a polynomial in the size of the underlying set and the largest
function value (not its length).
Research partially supported by a grant from the Natural Sciences and Engineering Research Council of Canada. |
| |
Keywords: | 05 B 99 68 C 25 |
本文献已被 SpringerLink 等数据库收录! |
|