Two-sided max-linear systems, game theory and the assignment problem.

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

• Daniel Jones (University of Birmingham)
• Wednesday 13 February 2019, 12:00-13:00
• Room R17/18, Watson building.

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

We define the two-sided max-linear system and we discuss real-life situations in which one may be interested in solving such systems. Interestingly, such systems lie in the complexity class NP intersect co-NP, one consequence of this is that it is not known whether the problem is polynomially solvable or not.

We briefly discuss why such systems may be of interest in the game theory community – discussing connections with mean-payoff games.

Finally, we show a surprising connection with the (polynomially solvable) assignment problem (AP). Is it possible that the AP could eventually be the key tool in solving two-sided max-linear systems?

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

This talk is included in these lists:

• Optimisation and Numerical Analysis Seminars
• Room R17/18, Watson building
• School of Mathematics events

Note that ex-directory lists are not shown.