### Article

## Semitractability of optimal stopping problems via a weighted stochastic mesh algorithm

In this paper, we propose a Weighted Stochastic Mesh (WSM) algorithm for approximating the value of discrete- and continuous-time optimal stopping problems. In this context, we consider tractability of such problems via a useful notion of semitractability and the introduction of a tractability index for a particular numerical solution algorithm. It is shown that in the discrete-time case the WSM algorithm leads to semitractability of the corresponding optimal stopping problem in the sense that its complexity is bounded in order by 𝜀^4 log^{𝑑+2}(1∕𝜀) with 𝑑 being the dimension of the underlying Markov chain. Furthermore, we study the WSM approach in the context of continuous- time optimal stopping problems and derive the correspond- ing complexity bounds. Although we cannot prove semi- tractability in this case, our bounds turn out to be the tightest ones among the complexity bounds known in the literature. We illustrate our theoretical findings by a numerical example.