Pseudo Expectation: A Tool for Analyzing Local Search Algorithms
Osamu Watanabe · Progress of Theoretical Physics Supplement · 2005
Watanabe et al. [Lecture Notes in Comp. Sci. 2827 (2004), 50] proposed pseudo expectation for analyzing relatively simple Markov processes that can be often seen as simple execution models of local search algorithms. In this paper, we first explain how it is used, and then investigate the approximation error bound of pseudo expectations.