Geodesic
Abstract tropical linear programming
Georg Loho1
1London School of Economics
The electronic journal of combinatorics, Tome 27 (2020) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

In this paper we develop a combinatorial abstraction of tropical linear programming. This generalizes the search for a feasible point of a system of min-plus-inequalities. We obtain an algorithm based on an axiomatic approach to this generalization. It builds on the introduction of signed tropical matroids based on the polyhedral properties of triangulations of the product of two simplices and the combinatorics of the associated set of bipartite graphs with an additional sign information. Finally, we establish an upper bound for our feasibility algorithm applied to a system of min-plus-inequalities in terms of the secondary fan of a product of two simplices. The appropriate complexity measure is a shortest integer vector in a cone of the secondary fan associated to the system.
DOI : 10.37236/7718
Classification : 14T90, 90C05, 52C40, 91A50, 05E45

Georg Loho  1

1 London School of Economics 
@article{10_37236_7718,
     author = {Georg Loho},
     title = {Abstract tropical linear programming},
     journal = {The electronic journal of combinatorics},
     year = {2020},
     volume = {27},
     number = {2},
     doi = {10.37236/7718},
     zbl = {1454.14157},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/7718/}
}
TY  - JOUR
AU  - Georg Loho
TI  - Abstract tropical linear programming
JO  - The electronic journal of combinatorics
PY  - 2020
VL  - 27
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/7718/
DO  - 10.37236/7718
ID  - 10_37236_7718
ER  - 
%0 Journal Article
%A Georg Loho
%T Abstract tropical linear programming
%J The electronic journal of combinatorics
%D 2020
%V 27
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/7718/
%R 10.37236/7718
%F 10_37236_7718
Georg Loho. Abstract tropical linear programming. The electronic journal of combinatorics, Tome 27 (2020) no. 2. doi: 10.37236/7718

Cité par Sources :