Prune and search

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

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. As such, it is a form of decrease and conquer algorithm, where at each step the decrease is by a constant factor. 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)), since summing a geometric series only multiplies by a constant factor, namely 1/(1-(1-p)) = 1/p.

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

References

  1. ↑ 1.0 1.1 N. Megiddo. Linear-time algorithms for linear programming in R3 and related problems. SIAM J. Computing, 12:759–776, 1983.
  2. ↑ Nimrod Megiddo, Linear Programming in Linear Time When the Dimension Is Fixed, 1984