Günter Rote:

The solution sets of extremal equations

Rechenzentrum Graz, Bericht 104, 1985, 58 pages.


The solution set of a system of equations where the + operation is replaced by max, has in general a unique maximum element but many minimal elements. The characterization of these minimal elements leads to a generalized set covering problem. The difference to the classical set covering problem is that, instead of taking a given set or not, one can select a set from a given chain of nested sets. We give several algorithms for enumerating the minimal solutions of the generalized set covering problem, all of them exponential in the worst case. When specialized to the set covering problem, the problem of enumerating the minimal solutions is also known as hypergraph dualization.

For the case of maxmin equations, we derive upper bounds on the number of solutions by using network flow techniques. We also disprove a conjecture of Czogala, Drewniak and Pedrycz (1982) that an n×n system of maxmin equations has less than 2n minimal solutions.

  pdf file (gzipped)
other papers about this subject
Last update: December 11, 2009.