A descent method for submodular function minimization

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 : D → R on a distributive lattice D ⊆ 2^V with ∅, V ∈ D 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 ∈ D such that x(Z) > f(Z). Given a submodular function f, by invoking the membership oracle O(|V|²) times, the descent method finds a sequence of subsets Z1, Z2, ..., Zk of V such that f(Z1) > f(Z2) > ... > f(Zk) = min{f(Y)|Y∈D}, where k is O(|V|²). The method furnishes an alternative framework for submodular function minimization if combined with possible efficient membership algorithms.