Prune and search is a method of solving optimization problems suggested by Nimrod Megiddo 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 In computer science, divide and conquer is an algorithm design paradigm. A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved dire ...

, 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 paramete ...

: :

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 particular, Megiddo himself used this approach in his linear time 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 relationships. Linear programming is ...

problem when the dimension is fixedNimrod Megiddo (1984)Linear Programming in Linear Time When the Dimension Is Fixed and for the

minimal enclosing sphere In mathematics, given a non-empty set of objects of finite extension in d-dimensional space, for example a set of points, a bounding sphere, enclosing sphere or enclosing ball for that set is an d-dimensional solid sphere containing all of these ...

problem for a set of points in space.

References

{{reflist Geometric algorithms Linear programming