Skip to Main content Skip to Navigation

Duality and Separation Theorems in Idempotent Semimodules

Abstract : We consider subsemimodules and convex subsets of semimodules over semirings with an idempotent addition. We introduce nonlinear projection on subsemimod- ules: the projection of a point is the maximal approximation from below of the point in the subsemimodule. We use this projection to separate a point from a convex set. We also show that the projection minimizes the analogue of Hilbert's projective metric. We develop more generally a theory of dual pairs for idempotent semimodules. We obtain as a corollary duality results between the row and column spaces of matrices with entries in idempotent semirings. We illustrate the results by showing polyhedra and half-spaces over the max-plus semiring.
Document type :
Complete list of metadata
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 7:14:32 PM
Last modification on : Friday, May 25, 2018 - 12:02:03 PM
Long-term archiving on: : Sunday, April 4, 2010 - 10:44:26 PM


  • HAL Id : inria-00071917, version 1



Guy Cohen, Stéphane Gaubert, Jean-Pierre Quadrat. Duality and Separation Theorems in Idempotent Semimodules. [Research Report] RR-4668, INRIA. 2002. ⟨inria-00071917⟩



Record views


Files downloads