The Structure of Optimal Solutions to the Submodular Function Minimization Problem
Abstract
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 Schrijver's 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 R(v) : x less than or equal to 0; x(A) less than or equal to f(A) for all A reflex subset contained in V}.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 23, 2003
- Accession Number
- ADA526806
Entities
People
- Collette Coullard
Organizations
- University of Minnesota