Ahlswede R., Wegener I. Search Problems

John Wiley, 1987. — 296 p. — (Wiley-Interscience series in discrete mathematics and optimization). — ISBN: 0-471-90825-8.Over the past thirty years there has been an increasing number of contributions to the topic of searching, both in theoretically as well as in applications- oriented journals. It is remarkable that very different kinds of problems are classified as search problems and that researchers from various fields often know little about results achieved in areas with which they are not familiar. In this book we attempt to present the extensive literature in such a way that the reader can quickly understand the range of questions and obtain a survey of them which is as comprehensive as possible.
Our goal was to treat the most important works in the field from the viewpoint of the current state of the science. However, we make no claim at all at completeness since the restraints of this book make such an attempt futile. For some works, which actually deserved to be presented in detail, we therefore settled for presenting the results. The interested researcher will then be in a position to find his own path through the literature. The book should be useful to the expert as a reference.
But our primary concern is to provide to every reader who is willing and able to engage in abstract, formal thought access to the basic ideas, methods and results in the field which have not yet appeared in book form but which deserve broader distribution due to their importance. Part 2 of the book is intended primarily for this broader group of readers. The only requirement here is a solid background in basic mathematics. All proofs are presented in great detail.Introductory Remarks and DefinitionsA sample search model
Search Problems with Error-free Tests
Binary search problems without restrictions on the tests
Alphabetic codes and binary search trees
Sorting problems
Weighting problems and geometric problems
Special search problems with error-free tests
[bSearch Problems Having Tests with Chance Errors[/b]
Stochastic approximation
Search problems having answers with chance errors and channels with feedback
Identification and ranking problems
Search Problems with Inspections
Minimizing expected search costs
Maximizing the probability of success with limited resources
More general models for search problems with inspections