Minimal

From Glossary

Jump to: navigation, search

In a partially ordered set, a minimal element is one that does not follow another in the ordering. This is not to be confused with minimum.

Another definition pertains to a subset with respect to some property such that no proper subset has that property. In the 0-1 knapsack problem the set of items not taken is minimal with respect to the greedy algorithm of adding the most valuable item, if it fits, until there are no more items than can fit. This does not necessarily produce a maximum objective value, but the converse is certainly true:  in order that LaTeX: x be an optimal solution, LaTeX: \{j: x_j=0\} must be minimal with respect to adding items that fit. See maximal for analogy and numerical example.


Views
Personal tools