In the design and analysis of
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
s for
combinatorial optimization
Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combi ...
, parametric search is a technique invented by for transforming a
decision algorithm (does this optimization problem have a solution with quality better than some given threshold?) into an
optimization algorithm
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 ...
(find the best solution). It is frequently used for solving optimization problems in
computational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems ar ...
.
Technique
The basic idea of parametric search is to simulate a ''test algorithm'' that takes as input a numerical parameter
, as if it were being run with the (unknown) optimal solution value
as its input. This test algorithm is assumed to behave
discontinuously when
, and to operate on its parameter
only by simple comparisons of
with other computed values, or by testing the sign of low-degree
polynomial function
In mathematics, a polynomial is an expression (mathematics), expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addition, subtrac ...
s of
. To simulate the algorithm, each of these comparisons or tests needs to be simulated, even though the
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
, and that determines whether
is above, below, or equal to the optimal solution value
.
Since the decision algorithm itself necessarily behaves discontinuously at
, the same algorithm can also be used as the test algorithm. However, many applications use other test algorithms (often,
comparison sort
A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation (often a "less than or equal to" operator or a three-way comparison) that determines which of two elements should occ ...
ing algorithms). Advanced versions of the parametric search technique use a
parallel algorithm
In computer science, a parallel algorithm, as opposed to a traditional serial algorithm, is an algorithm which can do multiple operations in a given time. It has been a tradition of computer science to describe serial algorithms in abstract machin ...
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.
Sequential test algorithm
In the most basic form of the parametric search technique, both the test algorithm and the decision algorithms are sequential (non-parallel) algorithms, possibly the same algorithm as each other. The technique simulates the test algorithm step by step, as it would run when given the (unknown) optimal solution value as its parameter
. Whenever the simulation reaches a step in which the test algorithm compares its parameter
to some other number
, it cannot perform this step by doing a numerical comparison, as it does not know what
is. Instead, it calls the decision algorithm with parameter
, and uses the result of the decision algorithm to determine the output of the comparison. In this way, the time for the simulation ends up equalling the product of the times for the test and decision algorithms. Because the test algorithm is assumed to behave discontinuously at the optimal solution value, it cannot be simulated accurately unless one of the parameter values
passed to the decision algorithm is actually equal to the optimal solution value. When this happens, the decision algorithm can detect the equality and save the optimal solution value for later output.
If the test algorithm needs to know the sign of a polynomial in
, this can again be simulated by passing the
roots of the polynomial to the decision algorithm in order to determine whether the unknown solution value is one of these roots, or, if not, which two roots it lies between.
An example considered both by and concerns a system of an odd number of particles, all moving rightward at different constant speeds along the same line. The median of the particles, also, will have a rightward motion, but one that is piecewise linear rather than having constant speed, because different particles will be the median at different times. Initially the particles, and their median, are to the left of the
origin
Origin(s) or The Origin may refer to:
Arts, entertainment, and media
Comics and manga
* Origin (comics), ''Origin'' (comics), a Wolverine comic book mini-series published by Marvel Comics in 2002
* The Origin (Buffy comic), ''The Origin'' (Bu ...
of the line, and eventually they and their median will all be to the right of the origin. The problem is to compute the time
at which the median lies exactly on the origin.
A
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 ...
decision algorithm is easy to define: for any time
, one can compute the position of each particle at time
and count the number of particles on each side of the origin. If there are more particles on the left than on the right, then