Name
Abstract | ||
|---|---|---|
A function f : R --> R is k-modal if its kth derivative has a unique zero. We study the problem of finding the smallest possible interval containing the unique zero of the kth derivative of such a function, assuming that the function is evaluated only at integer points. We present optimal algorithms for the case when k is even and for k = 3 and near-optimal algorithms when k greater than or equal to 5 and odd. A novel generalization of Kraft's inequality is used to prove lower bounds on the number of function evaluations required. We show how our algorithms lead to an efficient divide-and-conquer algorithm to determine all turning points or zeros of a k-modal function. Unbounded k-modal search is introduced and some problems in extending previous approaches for unbounded searching to the k-modal case are discussed. |
Year | DOI | Venue |
|---|---|---|
1996 | 10.1137/S0097539793246367 | SIAM JOURNAL ON COMPUTING |
Keywords | DocType | Volume |
k-modal search, Kraft's inequality, k-modal functions, optimal algorithms, binary search, unimodal search, bimodal search, unbounded search, Fibonacci numbers | Journal | 25 |
Issue | ISSN | Citations |
2 | 0097-5397 | 5 |
PageRank | References | Authors |
0.58 | 2 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anmol Mathur | 1 | 134 | 15.34 |
| Edward M. Reingold | 2 | 2214 | 563.65 |