Prune and search

Prune and search is a method of solving optimization problems suggested by Nimrod Megiddo in 1983.

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 0 < p < 1. Let n be the input size, T(n) be the time complexity of the whole prune-and-search algorithm, S(n) is the time complexity of the pruning step, then T(n) obeys the following recurrence relation:

$T(n)=S(n)+T(n(1-p)),\,$

which has the solution T(n) = O(S(n)).

In particular, Megiddo himself used this approach in his linear time algorithm for the linear programming problem when the dimension is fixed and for the minimal enclosing sphere problem for a set of points in space.

See also

• Divide and conquer algorithm