Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

Intitulé:   
Solving Simple Stochastic Games with few RandomNodes faster using Bland’s Rule
du groupe Séminaire Méthodes Formelles

Date 2019-06-25  11:00-12:00
TitreSolving Simple Stochastic Games with few RandomNodes faster using Bland’s Rule 
RésuméA simple stochastic game, SSG for short, is a two-player zero-sum game, a turn-based version of stochastic games. SSGs were introduced by Condon and provide a general framework that allows to study algorithmic complexity issues underlying reachability objectives. The best algorithm so far for solving SSGs is Ludwig’s randomized algorithm which works in expected 2^O(sqrt(n)) time. We first give a simpler iterative variant of this algorithm, using Bland’s rule from the simplex algorithm, which uses exponentially less random bits than Ludwig’s version. Then, we show how to adapt this method to the algorithm of Gimbert and Horn whose worst case complexity is O(k!), where k is the number of random nodes. Our algorithm has an expected running time of 2^O(k) , and works for general random nodes with arbitrary outdegree and probability distribution on outgoing arcs. 
Lieu178 
OrateurYann Strozecki 
Emailhttp://www.prism.uvsq.fr/~ystr/ 
UrlUniversité de Versailles Saint-Quentin 



Aucun document lié à cet événement.

Retour
Retour à l'index