Search Problems (Wiley Series in Discrete Mathematics and Optimization)

✍ Scribed by Rudolf Ahlswede, Ingo Wegener

• Publisher: John Wiley & Sons
• Year: 1987
• Tongue: English
• Leaves: 296
• Edition: 1
• Category: Library

✦ Synopsis

The problems of search, exploration, discovery, and identification are of key importance in a wide variety of applications, including engineering, computer science, economics, and information theory. Over the past 30 years a great deal of work has been done on search problems by scientists from several disciplines. This book brings together the results from a number of different fields to provide the first really comprehensive overview of the subject. Major emphasis is placed on applications in science and mathematics. Presents open problems and contains many suggestions for further reading.

✦ Table of Contents

Title Page......Page 3
Preface......Page 5
Preface to the English Edition......Page 7
Contents......Page 9
Part 1: Introductory Remarks and Definitions......Page 13
1. Introduction......Page 15
2. A sample search model......Page 17
Part 2: Search Problems with Error-Free Tests......Page 21
1. Introduction......Page 23
2. Nonsequential strategies and separating systems......Page 24
3. Random nonsequential strategies......Page 25
4. Sequential strategies and prefix codes......Page 28
5. Kraft's inequality and the noiseless-coding theorem......Page 30
6. Huffman's algorithm......Page 34
7. Optimal strategies with uniform distribution on the search domain......Page 38
1. Introduction......Page 41
2. Minimizing the search time in the worst case......Page 43
3. Good and optimal alphabetic codes......Page 44
4. Constructing optimal binary search trees......Page 53
5. The efficient construction of good binary search trees......Page 59
6. Lower bounds on the costs of optimal binary search trees......Page 65
7. Optimal binary search trees and optimal alphabetic codes with maximal costs......Page 71
1. Introduction......Page 77
2. Sorting a set with distinct elements......Page 79
3. Sorting a set of not necessarily distinct elements......Page 83
4. Sorting the disjoint union of two ordered sets......Page 86
5. The median problem......Page 89
6. The selection problem and the partition problem......Page 101
7. Yao's hypothesis......Page 103
8. The mass production of partial orders......Page 106
2. Finding a counterfeit coin with a beam balance......Page 111
3. Finding a counterfeit coin with an analytical balance......Page 113
4. Separating systems of sets with at most k elements......Page 115
5. Separating coins of various weights......Page 118
2. A medical search problem......Page 124
3. The questionnaire theory......Page 129
4. The number of available strategies......Page 131
Part 3: Search Problems having Tests with Chance Errors......Page 135
1. Introduction......Page 137
2. Approximate solution of equations by the Newton-Raphson rule......Page 138
3. The iteration method of v. Mises and Pollaczek-Geiringer......Page 140
4. The Robbins-Monro method of stochastic approximation......Page 142
5. Almost-everywhere convergence of the RM method......Page 146
6. Approximating the maximum of a regression function......Page 150
7. Dvoretzky's approximation method......Page 152
8. Estimations of the convergence rate of the RM method......Page 158
9. Sequential minimax search for the maximum of a unimodal function......Page 162
1. Introduction......Page 166
2. An equivalent information-theoretic problem......Page 170
3. An error-free method......Page 172
4. Shannon's coding theorem......Page 175
5. Feedback does not increase the capacity of discrete memoryless channels......Page 177
6. A block-coding method: information as list reduction......Page 180
7. A robust model......Page 186
8. A Bayes method......Page 188
9. A common generalization of the noiseless-coding theorem and Shannon's coding theorem, sequential methods......Page 189
10. Gaussian channels with feedback and stochastic approximation......Page 194
1. Introduction......Page 199
2. A model for general sequential multi-decision problems......Page 203
3. Upper bounds for the expected loss......Page 204
4. Conditions for the finiteness of the average sample number and its higher moments......Page 207
5. A lower bound on the average sample number for a multi-decision problem......Page 210
6. The ordering theorem......Page 212
7. Identification problems and their algebraic structure......Page 216
8. A fundamental sequential decision procedure......Page 219
9. Special identification problems......Page 222
10. Paulson's sequential procedure for selecting the population with the largest expected value from k normal distributed populations......Page 225
Part 4: Search Problems with Inspections......Page 229
1. Introduction......Page 231
2. The existence of successful strategies with finite expected search costs......Page 235
3. Methods for improving existing strategies......Page 237
4. The existence and the construction of optimal strategies......Page 239
5. The class of pseudostrategies......Page 244
6. Constructing almost-optimal strategies......Page 247
1. Introduction......Page 248
3. Can there be fast algorithms for solving the problem?......Page 250
4. Bounds for the maximal probability of success and dividing the problem in subproblems......Page 252
5. An algorithm for constructing an optimal allocation......Page 255
6. The analysis of the algorithm......Page 257
2. Almost periodic strategies......Page 260
3. Optimal strategies for locating the object being sought......Page 262
5. Continuous search problems with inspections......Page 264
6. Searching for one of several objects......Page 268
7. Search problems with random parameters......Page 271
8. Search and stop problems......Page 272
9. Search problems with positive switch costs......Page 276
10. Searching for a nonstationary object......Page 277
11. Searching without being discovered......Page 279
12. Linear search......Page 281
References......Page 283
Further Reading......Page 290
Index......Page 294