In the design and analysis of algorithms for combinatorial optimization, parametric search is a technique invented by Nimrod Megiddo in 1983 for transforming a decision algorithm (does this optimization problem have a solution with quality better than some given threshold?) into an optimization algorithm (find the best solution). It is frequently used for solving optimization problems in computational geometry.
Technique The basic idea of parametric search is to simulate a test algorithm that takes as input a numerical parameter X {\displaystyle X} , as if it were being run with the (unknown) optimal solution value X ∗ {\displaystyle X^{*}} as its input. This test algorithm is assumed to behave discontinuously when X = X ∗ {\displaystyle X=X^{*}} , and to operate on its parameter X {\displaystyle X} only by simple comparisons of X {\displaystyle X} with other computed values, or by testing the sign of low-degree polynomial functions of X {\displaystyle X} . To simulate the algorithm, each of these comparisons or tests needs to be simulated, even though the X {\displaystyle X} of the simulated algorithm is unknown. To simulate each comparison, the parametric search applies a second algorithm, a decision algorithm, that takes as input another numerical parameter Y {\displaystyle Y} , and that determines whether Y {\displaystyle Y} is above, below, or equal to the optimal solution value X ∗ {\displaystyle X^{*}} . Since the decision algorithm itself necessarily behaves discontinuously at X ∗ {\displaystyle X^{*}} , the same algorithm can also be used as the test algorithm. However, many applications use other test algorithms (often, comparison sorting algorithms). Advanced versions of the parametric search technique use a parallel algorithm as the test algorithm, and group the comparisons that must be simulated into batches, in order to significantly reduce the number of instantiations of the decision algorithm.
… excerpt ends here. Continue reading the full article.
