Charging argument

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.

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.

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 = {I₁, I₂, ... , I_n}, where each interval I_i ∈ I has a starting time s_i and a finishing time f_i, where s_i < f_i, the goal is to find a maximal subset of mutually compatible intervals in I. Here, two intervals I_j and I_k are said to be compatible if they do not overlap, in that s_j < f_j ≤ s_k < f_k.

...
Wikipedia