A descent method for submodular function minimization |
| |
| Authors: | Satoru Fujishige Satoru Iwata |
| |
| Institution: | (1) Division of Systems Science, Graduate School of Engineering Science, Osaka University, Toyonaka, Osaka 560-8531 Japan, JP;(2) Department of Mathematical Informatics, Graduate School of Information Science and Technology, University of Tokyo, Tokyo 113-0033, Japan, JP |
| |
| Abstract: | We show a descent method for submodular function minimization based on an oracle for membership in base polyhedra. We assume
that for any submodular function f: ?→R on a distributive lattice ?⊆2
V
with ?,V∈? and f(?)=0 and for any vector x∈R
V
where V is a finite nonempty set, the membership oracle answers whether x belongs to the base polyhedron associated with f and that if the answer is NO, it also gives us a set Z∈? such that x(Z)>f(Z). Given a submodular function f, by invoking the membership oracle O(|V|2) times, the descent method finds a sequence of subsets Z
1,Z
2,···,Z
k
of V such that f(Z
1)>f(Z
2)>···>f(Z
k
)=min{f(Y) | Y∈?}, where k is O(|V|2). The method furnishes an alternative framework for submodular function minimization if combined with possible efficient
membership algorithms.
Received: September 9, 2001 / Accepted: October 15, 2001?Published online December 6, 2001 |
| |
| Keywords: | : submodular function – base polyhedron – descent method |
| 本文献已被 SpringerLink 等数据库收录！ |
|
