Prune and search is a method of solving

optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...

problems suggested by

Nimrod Megiddo , birth_date = , birth_place = , death_date = , death_place = , citizenship = , field = Operations researchAlgorithms ComplexityMachine learning Game theory , workplaces = IBM Research ...

in 1983.Nimrod Megiddo (1983) Linear-time algorithms for linear programming in R³ and related problems. SIAM J. Comput., 12:759–776 The basic idea of the method is a recursive procedure in which at each step the input size is reduced ("pruned") by a constant factor . As such, it is a form of decrease and conquer algorithm, where at each step the decrease is by a constant factor. Let be the input size, be the

time complexity In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

of the whole prune-and-search algorithm, and be the time complexity of the pruning step. Then obeys the following

recurrence relation In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter ...

: :

T(n) = S(n) + T(n(1-p)).

This resembles the recurrence for

binary search In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the m ...

but has a larger term than the constant term of binary search. In prune and search algorithms S(n) is typically at least linear (since the whole input must be processed). With this assumption, the recurrence has the solution . This can be seen either by applying the master theorem for divide-and-conquer recurrences or by observing that the times for the recursive subproblems decrease in a

geometric series In mathematics, a geometric series is the sum of an infinite number of terms that have a constant ratio between successive terms. For example, the series :\frac \,+\, \frac \,+\, \frac \,+\, \frac \,+\, \cdots is geometric, because each succ ...

. In particular, Megiddo himself used this approach in his

linear time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

algorithm for the

linear programming Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear function#As a polynomial function, li ...

problem when the dimension is fixedNimrod Megiddo (1984)Linear Programming in Linear Time When the Dimension Is Fixed and for the minimal enclosing sphere problem for a set of points in space.

References

{{reflist Geometric algorithms Linear programming