Charging Argument

In computer science, a Charging Argument is used to compare an algorithm output to an optimal solution.

Example

Proving optimality for earliest finishing time greedy algorithm:

The charging argument wants to charge each interval of an optimal to a unique interval in the greedy solution. Let OPT be any optimal solution and S the solution of the EFT greedy algorithm. We want to define a one to one function h : OPT→ S. Define h: Let h(J) be that interval J′ in S that intersects J and has the earliest finishing time amongst intervals in S intersecting J. First we claim that h is a function. Second we claim h is one to one. Suppose both J1 and J2 in OPT are mapped to the same J′ in S and without loss of generality assume that f1 < f2 where f1 (resp f2) is the finishing time of J(1) (resp. J(2)). Let f′ be the finishing time of J′. By the definition of the mapping h, f′ <= f1 or else the greedy EFT algorithm would have taken J1 (and not J′). So we have f′ <= f1 < f2 and since J1 and J2 cannot intersect, J2 cannot intersect J′.

Sources

Allan Borodin [PDF document]. Retrieved from Lecture Notes Online Web site: http://www.cs.toronto.edu/~bor/373s11/L2.pdf