Article citationsMore>>

B. Verkhovsky, “Optimal Algorithm for Search of a Maximum of n-Modal Function on Infinite Interval,” In: D. Du and P. M. Pardalos, Eds., Minimax and Applications, Academic Publisher, Kluwer, 1997, pp. 245-261.

has been cited by the following article:

• TITLE: Parallel Minimax Searching Algorithm for Extremum of Unimodal Unbounded Function

  AUTHORS: Boris S. Verkhovsky

  KEYWORDS: Adversarial Minimax Analysis, Design Parameters, Dynamic Programming, Function Evaluation, Optimal Algorithm, Parallel Algorithm, System Design, Statistical Experiments, Time Complexity, Unbounded Search, Unimodal Function

  JOURNAL NAME: International Journal of Communications, Network and System Sciences, Vol.4 No.9, September 23, 2011

  ABSTRACT: In this paper we consider a parallel algorithm that detects the maximizer of unimodal function f(x) computable at every point on unbounded interval (0, ∞). The algorithm consists of two modes: scanning and detecting. Search diagrams are introduced as a way to describe parallel searching algorithms on unbounded intervals. Dynamic programming equations, combined with a series of liner programming problems, describe relations between results for every pair of successive evaluations of function f in parallel. Properties of optimal search strategies are derived from these equations. The worst-case complexity analysis shows that, if the maximizer is located on a priori unknown interval (n-1], then it can be detected after cp(n)=「2log「p/2」+1(n+1)」-1 parallel evaluations of f(x), where p is the number of processors.