Matroid Optimisation Problem

Definition

Matroid Optimisation Problem

A matroid optimisation problem is an optimisation problem in which the feasible solutions are the independent sets of a matroid $M=(E,\mathcal{I})$.

Given a weight function

$$\omega :E\to \mathbb{R},$$

the weight of an independent set $I\in \mathcal{I}$ is typically defined additively as

$$\omega (I)=\sum _{e\in I}\omega (e).$$