The Structure of Optimal Solutions to the Submodular Function Minimization Problem
MINNESOTA UNIV MINNEAPOLIS INST FOR MATHEMATICS AND ITS APPLICATIONS
Pagination or Media Count:
In this paper, we study the structure of optimal solutions to the submodular function minimization problem. We introduce prime sets and pseudoprime sets as basic building block of minimizer sets, and investigate composition, decomposition, recognition, and certification of prime sets. We show how Schrijvers submodular function minimization algorithm can be modified to construct in polynomial time a prime or pseudoprime decomposition of the ground set. We also show that the final vector x obtained by this algorithm is an extreme point of the polyhedron P x epsilon Rv x less than or equal to 0 xA less than or equal to fA for all A reflex subset contained in V.
- Theoretical Mathematics