From Glossary

Jump to: navigation, search

In a partially ordered set, a maximal element is one for which no element follows it in the ordering. This is not to be confused with maximum. For example, consider the following knapsack problem:

LaTeX: \max \{ 5x + y: (x, y) in \mathbb{Z}^2, \, x \ge 0, \, y \ge 0,  3x + 2y \le 3\}.

The maximum value is LaTeX: 5, with LaTeX: (x, y) = (1, 0). Define the partial ordering to be the ordinary greater-than-or-equal-to, so that LaTeX: (x',y') > (x, y) means LaTeX: x' \ge x, LaTeX: y' \ge y, and either LaTeX: x' > x or LaTeX: y' > y. In words, LaTeX: (x', y') > (x, y) means we can put at least one more item into the knapsack, in which case we would increase our return. When we cannot do so, LaTeX: (x, y) is a maximal element. In particular, LaTeX: (0,1) is a maximal element, and its value is LaTeX: 1, which is not the maximum.

Another definition pertains to a subset with respect to some property such that no proper superset has that property. In the 0-1 knapsack problem with LaTeX: n variables, we define the subset of items taken (for any solution) as LaTeX: J=\{j: x_j=1\}. Then, we define LaTeX: J as maximal if no item can be added without violating the limit, i.e., LaTeX: \textstyle a_k > b - \sum_{j\in J} a_j for all LaTeX: k not in LaTeX: J.

Personal tools