Naive Greedy¶
Given a set of items \(V = \{1, 2, 3, \cdots, n\}\) which we also call the Ground Set, define a utility function (set function) \(f:2^V \rightarrow \Re\), which measures how good a subset \(X \subseteq V\) is. Let \(c :2^V \rightarrow \Re\) be a cost function, which describes the cost of the set (for example, the size of the subset). The goal is then to have a subset \(X\) which maximizes \(f\) while simultaneously minimizing the cost function \(c\). It is easy to see that maximizing a generic set function becomes computationally infeasible as \(V\) grows. Often the cost \(c\) is budget constrained (for example, a fixed set summary) and a natural formulation of this is the following problem:
For any SetFunction, naive greedy maximization can be achieved by calling maximize() with optimizer=’NaiveGreedy’. The naive greedy optimizer implementation in this library implements the standard greedy algorithm [Min78]. It starts with an empty set and in every iteration adds to it a new element from the ground set with maximum marginal gain until the desired budget (budget) is achieved or the best gain in any iteration is zero (stopIfZeroGain) or negative (stopIfNegativeGain). The solution thus obtained is called a greedy solution.
Note
Unless the marginal gain of the element at each step is unique, the greedy solution will not be unique. In such a case, the current implementation adds the first best element encountered at every iteration. As unordered sets are used to represent the ground sets, this ordering need not be unique.