Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information
Date and Time: Thursday, April 19, 2007, 12:15 pm
Duration: This information is not available in the database
Location: OAT S15/S16/S17
Speaker: Rahul Savani (Department of Computer Science, Univ. of Warwick, UK)
We present discounted payoff games, which are one of a number of two-player zero-sum games of infinite duration played on finite graphs that have the property that the natural associated decision problem is in NP and coNP, yet no polynomial-time algorithms are known. We then present the P-matrix linear complementarity problem (LCP), for which the existence of a polynomial-time algorithm is also a major open problem. LCPs generalize LPs and the bimatrix game equilibrium problem. Finally, we present a simple reduction from discounted payoff games to P-matrix LCPs.
Joint work with Hugo Gimbert and Marcin Jurdziński.
Automatic MiSe System Software Version 1.4803M | admin login