A Structure Theory for the Parametric Submodular Intersection Problem

A linearly parameterized polymatroid intersection problem appears in the context of principal partitions. We consider a submodular intersection problem on a pair of strong-map sequences of submodular functions, which is an extension of the linearly parameterized polymatroid intersection problem to a nonlinearly parameterized one. We introduce the concept of a basis frame on a finite nonempty set of cardinality n that gives a mapping from the set of all base polyhedra in n-dimensional space into n-dimensional vectors such that each base polyhedron is mapped to one of its bases. We show the existence of a simple universal representation of all optimal solutions of the parameterized submodular intersection problem by means of basis frames.