Game-Theoretic Techniques
Lists
Only you see this
Abstract
IN this chapter we study several ideas that are basic to the design and analysis of randomized algorithms. All the topics in this chapter share a game-theoretic viewpoint, which enables us to think of a randomized algorithm as a probability distribution on deterministic algorithms. This leads to the Yao ‘s Minimax Principle, which can be used to establish a lower bound on the performance of a randomized algorithm.
BibTeX
@inproceedings{motwani1995game,
author = {Rajeev Motwani and Prabhakar Raghavan},
title = {{Game-Theoretic Techniques}},
booktitle = {Cambridge},
year = {1995},
doi = {10.1017/cbo9780511814075.003},
}Loading related content...