Set coverings and invertibility of Functional Galois Connections

Akian, Marianne; Gaubert, Stephane; Kolokoltsov, Vassili

Set coverings and invertibility of Functional Galois Connections

Authors

Akian, Marianne

Gaubert, Stephane

Kolokoltsov, Vassili

Description

We consider equations of the form Bf=g, where B is a Galois connection between lattices of functions. This includes the case where B is the Legendre-Fenchel transform, or more generally a Moreau conjugacy. We characterise the existence and uniqueness of a solution f in terms of generalised subdifferentials. This extends a theorem of Vorobyev and Zimmermann, relating solutions of max-plus linear equations and set coverings. We give various illustrations.
33 pages, 2 Postscript figures; Acknowledgement added