In computer science, a charging argument is used to compare the output of an optimization algorithm to an optimal solution. It is typically used to show that an algorithm produces optimal results by proving the existence of a particular injective function. For profit maximization problems, the function can be any one-to-one mapping from elements of an optimal solution to elements of the algorithm's output. For cost minimization problems, the function can be any one-to-one mapping from elements of the algorithm's output to elements of an optimal solution.
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| denote the profit of the algorithm's output given an input I, and let |OPT| denote the profit of an optimal solution for I. If an injective function h : OPT → A exists, it follows that |OPT|≤|A|. 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| and |OPT| denote the cost of the algorithm's output and optimal solution respectively, then the existence of an injective function h : A → OPT would mean that |A|≤|OPT|. 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.
Variations
Charging arguments can also be used to show approximation results. In particular, it can be used to show that an algorithm is an n-approximation to an optimization problem. Instead of showing that an algorithm produces outputs with the same value of profit or cost as the optimal solution, show that it attains that value within a factor of n. Rather than proving the existence of a one-to-one function, the charging argument focuses on proving that an n-to-one function exists in order to prove approximation results.
Given a set of n intervals I = , where each interval Ii ∈ I has a starting time si and a finishing time fi, where si < fi, the goal is to find a maximal subset of mutually compatible intervals in I. Here, two intervals Ij and Ik are said to be compatible if they do not overlap, in that sj < fj ≤ sk < fk. Consider the earliest finish time greedy algorithm, described as follows:
Sort the intervals in I by ascending finishing times.
Consider each interval in I in sorted order. Add the interval into the set if it does not conflict with intervals already contained in the set. Otherwise, disregard the interval.
The interval scheduling problem can be viewed as a profit maximization problem, where the number of intervals in the mutually compatible subset is the profit. The charging argument can be used to show that the earliest finish time algorithm is optimal for the interval scheduling problem. Given a set of intervals I = , let OPT be any optimal solution of the interval scheduling problem, and let EFT be the solution of the earliest finishing time algorithm. For any interval J ∈ OPT, define h as the interval J' ∈ EFT that intersects J with the earliest finishing time amongst all intervals in EFT intersecting J. To show that the earliest finish time algorithm is optimal using the charging argument, h must be shown to be a one-to-one function mapping intervals in OPT to those in EFT. Suppose J is an arbitrary interval in OPT. Show that h is a function mapping OPT to EFT. Show that h is one-to-one. Therefore, h is a one-to-one function mapping intervals in OPT to those in EFT. By the charging argument, the earliest finishing time algorithm is optimal.
Job Interval Scheduling Problem
Consider the job interval scheduling problem, an NP-hard variant of the interval scheduling problem visited earlier. As before, the goal is to find a maximal subset of mutually compatible intervals in a given set of n intervals, I = . Each interval Ii ∈ I has a starting time si, a finishing time fi, and a job classci. Here, two intervals Ij and Ik are said to be compatible if they do not overlap and have different classes. Recall the earliest finishing time algorithm from the previous example. After modifying the definition of compatibility in the algorithm, the charging argument can be used to show that the earliest finish time algorithm is a 2-approximation algorithm for the job interval scheduling problem. Let OPT and EFT denote the optimal solution and the solution produced by the earliest finishing time algorithm, as earlier defined. For any interval J ∈ OPT, define h as follows: To show that the earliest finish time algorithm is a 2-approximation algorithm using the charging argument, h must be shown to be a two-to-one function mapping intervals in OPT to those in EFT. Suppose J is an arbitrary interval in OPT. Show that h is a function mapping OPT to EFT. Show that h is two-to-one. Therefore, h maps no more than two distinct intervals in OPT to the same interval in EFT, and so h is two-to-one. By the charging argument, the earliest finishing time algorithm is a two-approximation algorithm for the job interval scheduling problem.
