Georg Loho: Abstract tropical linear programming and matching fields

It is a major open question if the feasibility problem for tropical linear inequality systems, which is in NP and in co-NP, can be solved in polynomial time.
To get a deeper understanding of the problem, we introduce signed tropical matroids which encode and generalize the combinatorics of a tropical linear inequality system.
These signed tropical matroids are based on (non-regular) triangulations of a product of two simplices.
We show that an algorithm similar to the simplex method can be used to solve the feasibility problem for this generalized setting. It turns out that the main method only depends on matching fields deduced from the triangulation.