Best approximation in max-plus semimodules

Marianne Akian; Stéphane Gaubert; Viorel Niţicǎ; Ivan Singer

doi:10.1016/j.laa.2011.06.009

Best approximation in max-plus semimodules

Marianne Akian, Stéphane Gaubert, Viorel Niţicǎ, Ivan Singer

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Pages (from-to)	3261-3296
Number of pages	36
Journal	Linear Algebra and Its Applications
Volume	435
Issue number	12
DOIs	https://doi.org/10.1016/j.laa.2011.06.009
Publication status	Published - 15 Dec 2011

Keywords

Distance to half-space
Elements of best approximation
Hilbert's projective metric
Max-plus algebra
Max-plus linear inequalities
Max-plus projectors
Tropical algebra

Access to Document

10.1016/j.laa.2011.06.009

Cite this

@article{7403bd5c6a284f6db677692ff3a8b328,

title = "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.",

keywords = "Distance to half-space, Elements of best approximation, Hilbert's projective metric, Max-plus algebra, Max-plus linear inequalities, Max-plus projectors, Tropical algebra",

author = "Marianne Akian and St{\'e}phane Gaubert and Viorel Ni{\c t}icǎ and Ivan Singer",

year = "2011",

month = dec,

day = "15",

doi = "10.1016/j.laa.2011.06.009",

language = "English",

volume = "435",

pages = "3261--3296",

journal = "Linear Algebra and Its Applications",

issn = "0024-3795",

number = "12",

}

TY - JOUR

T1 - Best approximation in max-plus semimodules

AU - Akian, Marianne

AU - Gaubert, Stéphane

AU - Niţicǎ, Viorel

AU - Singer, Ivan

PY - 2011/12/15

Y1 - 2011/12/15

N2 - 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.

AB - 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.

KW - Distance to half-space

KW - Elements of best approximation

KW - Hilbert's projective metric

KW - Max-plus algebra

KW - Max-plus linear inequalities

KW - Max-plus projectors

KW - Tropical algebra

U2 - 10.1016/j.laa.2011.06.009

DO - 10.1016/j.laa.2011.06.009

M3 - Article

AN - SCOPUS:80051582413

SN - 0024-3795

VL - 435

SP - 3261

EP - 3296

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

IS - 12

ER -

Best approximation in max-plus semimodules

Abstract

Keywords

Access to Document

Fingerprint

Cite this