Charging Argument
Encyclopedia
In computer science
, a Charging Argument is used to compare an algorithm output to an optimal solution.
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′.
[PDF document]. Retrieved from Lecture Notes Online Web site: http://www.cs.toronto.edu/~bor/373s11/L2.pdf
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, 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 BorodinAllan Borodin
Allan Bertram Borodin is a University of Toronto professor whose research is in computational complexity theory and algorithms.He has co-authored papers with some of the best researchers in computer science including his longtime friend and colleague Turing Award winner Stephen Cook...
[PDF document]. Retrieved from Lecture Notes Online Web site: http://www.cs.toronto.edu/~bor/373s11/L2.pdf