Abstract tropical linear programming

Georg Loho*

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

2 Downloads (Pure)

Abstract

In this paper we develop a combinatorial abstraction of tropical linear pro-gramming. 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 infor-mation. 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.

Original languageEnglish
Article numberP2.51
Pages (from-to)1-68
Number of pages68
JournalElectronic journal of combinatorics
Volume27
Issue number2
DOIs
Publication statusPublished - 2020
Externally publishedYes

Fingerprint

Dive into the research topics of 'Abstract tropical linear programming'. Together they form a unique fingerprint.

Cite this