Maximal versus Maximum:
About Boolean MAX-CSP assignments.
No limitation on which relations used.
Defn.
An assignment J for Boolean CSP-formula F is maximal if E(Z(F,b)) is maximum for b=0, i.e., E(Z(F,0)) >= E(Z(F,b)) for b>0.
Defn.
An assignment J for Boolean CSP-formula F is maximum if there is no
better assignment.
Facts:
Finding a maximal assignment is polynomial-time.
Finding a maximum assignment is NP-hard.
A maximum assignment can be transformed in polynomial time into a maximal
assignment for an equally satisfiable formula F'.
Uses of maximal versus maximum in other contexts:
About matchings:
Defn. M is maximal if there is no matching M0 subset M such that M0 is a matching
(i.e., no edge can be added to M without violating the
matching condition).
Defn. M is maximum if there is no matching M0 such that size(M0)>size(M) (i.e.,
there is no matching larger than M in sense of cardinality).
A matching can be maximal without being maximum
(the Z example)