The Polymatroid Representation of a Greedoid, and Associated Galois Connections
For researchers in combinatorial optimization, this work provides theoretical foundations for greedoids that bridge matroids and polymatroids, though it is incremental in nature.
The paper develops the theory of polymatroid greedoids, proving that every local poset greedoid with correct greedy optimization has a polymatroid representation, and identifies a subclass called strong polymatroid greedoids with favorable properties.
A greedoid is a generalization of a matroid allowing for more flexible analyses and modeling of combinatorial optimization problems. However, these structures decimate many matroid properties contributing to their pervasive nature. A polymatroid greedoid [KL85] presents an interesting middle ground, so we further develop this class. First we prove every local poset greedoid for which the greedy algorithm correctly solves linear optimizations over its basic words must have a polymatroid representation. For this, we use relationships between the lattices of greedoid flats and closed sets of a polymatroid to generalize concepts in [KL85]. Then, we show our generalization is defined by a Galois connection between the greedoid flats and closed sets of a representation. Finally, we apply this duality to identify a subclass of polymatroid greedoids with favorable properties, which we call strong polymatroid greedoids. As technical tools for our analyses, we introduce optimism and the Forking Lemma for interval greedoids. Both are pervasive in our work, and are of independent interest.