Correctness
In order for an algorithm to optimally solve a profit maximization problem, the algorithm must produce an output that has as much profit as the optimal solution for every possible input. Let |A(I)| denote the profit of the algorithm's output given an input I, and let |OPT(I)| denote the profit of an optimal solution for I. If an injective function h : OPT(I) → A(I) exists, it follows that |OPT(I)| ≤ |A(I)|. Since the optimal solution has the greatest profit attainable, this means that the output given by the algorithm is just as profitable as the optimal solution, and so the algorithm is optimal.
The correctness of the charging argument for a cost minimization problem is symmetric. If |A(I)| and |OPT(I)| denote the cost of the algorithm's output and optimal solution respectively, then the existence of an injective function h : A(I) → OPT(I) would mean that |A(I)| ≤ |OPT(I)|. Since the optimal solution has the lowest cost, and the cost of the algorithm is the same as the cost of the optimal solution of the minimization problem, then the algorithm also optimally solves the problem.
Read more about this topic: Charging Argument
Famous quotes containing the word correctness:
“With impressive proof on all sides of magnificent progress, no one can rightly deny the fundamental correctness of our economic system.”
—Herbert Hoover (1874–1964)
“The surest guide to the correctness of the path that women take is joy in the struggle. Revolution is the festival of the oppressed.”
—Germaine Greer (b. 1939)
“What will happen once the authentic mass man takes over, we do not know yet, although it may be a fair guess that he will have more in common with the meticulous, calculated correctness of Himmler than with the hysterical fanaticism of Hitler, will more resemble the stubborn dullness of Molotov than the sensual vindictive cruelty of Stalin.”
—Hannah Arendt (1906–1975)