Search Results

Optimal selections in a decision process are often constrained by prerequisites. However, such prerequisites can encode functional rather than literal dependencies, so a required dependency may be supplied by one or several interacting alternatives. We introduce matroidal prerequisite systems (MPS), a combinatorial constraint structure where a poset specifies prerequisites while a matroid determines when those prerequisites have been satisfied by its span. This creates an order-sensitive notion of feasibility over words, where feasible words are associated with independent sets, while dependencies may be fulfilled through substitutable functionality. Our main contribution is approximation algorithms for nonnegative additive maximization and monotone submodular maximization over the feasible words of an MPS. The guarantees are determined by two structural parameters: the maximum matroid rank Δ of a principal ideal in the poset and the maximum matroid connectivity λ_max. These measure the distance an MPS is from encoding a matroid or a poset antimatroid, respectively, both of which are generalized by an MPS. For additive maximization, we obtain deterministic Δ- and (1+λ_max)-approximation algorithms. By extending these techniques, we obtain efficient deterministic (2+λ_max)-approximation and randomized (Δ²⋅(1-1/e-δ)^{-1})-approximation algorithms for all δ > 0 for submodular maximization. The algorithm design and analysis use the theory of polymatroid greedoids, via a cryptomorphism we prove between an MPS and a strong polymatroid greedoid. Finally, a reduction from densest k-subgraph shows it is not possible to efficiently compute a min{Δ,λ_max}^o(1)-approximation to nonnegative additive maximization over the feasible words of an MPS under the Gap Exponential Time Hypothesis. Thus, an MPS provides a tractable, but provably nontrivial, framework for combinatorial optimization with interacting prerequisites, independence, and substitution.