Tropical Mathematics and Combinatorial Optimisation

Add to your list(s) Download to your calendar using vCal

• Peter Butkovic (School of Mathematics, University of Birmingham)
• Thursday 09 November 2017, 12:00-13:00
• LTB Watson.

If you have a question about this talk, please contact Sergey Sergeev.

Tropical mathematics has emerged as a new, unconventional modelling and solution tool for a variety of theoretical and practical problems ranging from computer science, biology and phylogenetic to production scheduling, railway scheduling and cryptography.

We will present a selection of links between tropical mathematics and combinatorial optimisation indicating potential of tropical methodology for combinatorial optimisation problems. These will include:

1. Interpretation of the maximum cycle mean in a directed graph as a key concept in the tropical spectral theory. This enables us to easily and straightforwardly derive some formulae such as the maximum cycle mean of a matrix power.

2. Usual longest/shortest distances matrix can be found by a repeated tropical squaring of the direct distances matrix.

3. Efficient description of the complete solution set to a system of dual (Afriat) inequalities. This provides a tool for finding solutions satisfying specific requirements such as integrality.

4. Efficient description of the Hungarian (assignment problem) scaling which, in addition to the usual scaling, enables us to strictly visualize AP-active entries.

5. Optimal assignment problem value coincides with the tropical permanent of a matrix, which (due to the absence of subtraction) assumes the role of a determinant and becomes a tool for analysing systems of tropical equations and tropical linear independence, with uniqueness and parity of optimal permutations playing a key role. In this respect new variants of the classical assignment problem of unresolved computational complexity have been introduced (parity assignment problem, best AP principal submatrix problem).

This talk is part of the Optimisation and Numerical Analysis Seminars series.

This talk is included in these lists:

• LTB Watson
• Optimisation and Numerical Analysis Seminars
• School of Mathematics events

Note that ex-directory lists are not shown.