Best approximation in max-plus semimodules

Abstract

We establish new results concerning projectors on max-plus spaces, as well as separating half-spaces, and derive an explicit formula for the distance in Hilbert's projective metric between a point and a half-space over the max-plus semiring, as well as explicit descriptions of the set of minimizers. As a consequence, we obtain a cyclic projection type algorithm to solve systems of max-plus linear inequalities.

42 pages and 4 figures

References in corpus (2)

• Duality and separation theorems in idempotent semimodules
• Tropical polar cones, hypergraph transversals, and mean payoff games

Cited by in corpus (18)

• Tropicalizing the simplex algorithm
• Convexity in Tree Spaces
• Tropical Fermat-Weber points
• The level set method for the two-sided eigenproblem
• Tropical implementation of the Analytical Hierarchy Process decision method
• Characterization of tropical hemispaces by (P,R)-decompositions
• Tropical Geometric Variation of Phylogenetic Tree Shapes
• Algebraic solution of tropical best approximation problems
• Quasi--Euclidean classification of Alcoved Convex Polyhedra
• Tropical Gaussians: A Brief Survey
• An Invitation to Tropical Alexandrov Curvature
• On solution of tropical discrete best approximation problems
• Tropical Geometry and Piecewise-Linear Approximation of Curves and Surfaces on Weighted Lattices
• Alternating Minimization for Regression with Tropical Rational Functions
• Tropical Data Science
• Beyond Value Iteration for Parity Games: Strategy Iteration with Universal Trees
• Tropical solution of discrete best approximation problems
• Tree Topologies along a Tropical Line Segment