Günter Rote:
The solution sets of extremal equations
Rechenzentrum Graz, Bericht 104, 1985, 58 pages.
Abstract
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.
Last update: December 11, 2009.