Charging Argument - Correctness

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:

    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)

    Rather would I have the love songs of romantic ages, rather Don Juan and Madame Venus, rather an elopement by ladder and rope on a moonlight night, followed by the father’s curse, mother’s moans, and the moral comments of neighbors, than correctness and propriety measured by yardsticks.
    Emma Goldman (1869–1940)

    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)