Algorithms and Conditional Lower Bounds for Planning Problems

Krishnendu Chatterjee, Wolfgang Dvořák, Monika Henzinger +1

We consider planning problems for graphs, Markov decision processes (MDPs), and games on graphs. While graphs represent the most basic planning model, MDPs represent interaction wi…