MAXIMAL

Maximal - 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 :

The maximum value is 5, with (x, y) = (1, 0). Define the partial ordering to be the ordinary greater-than-or-equal-to, so that (x', y') > (x, y) means x' >= x,y' >= y, and either x' > x or y' > y. In words, (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, (x, y) is a maximal element. In particular, (0,1) is a maximal element, and its value is 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 n variables, we define the subset of items taken (for any solution) as J=(j: x_j=1). Then, we define J as maximal if no item can be added without violating the limit     i.e., a_k > b     sum_j in J a_j   for all k not in J.