University of Birmingham > Talks@bham > Optimisation and Numerical Analysis Seminars > Two-sided max-linear systems, game theory and the assignment problem.

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

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

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

Talks@bham, University of Birmingham. Contact Us | Help and Documentation | Privacy and Publicity.
talks@bham is based on talks.cam from the University of Cambridge.