computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, 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
In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contrapositiv ...
. For
profit maximization
In economics, profit maximization is the short run or long run process by which a firm may determine the price, input and output levels that will lead to the highest possible total profit (or just profit in short). In neoclassical economics, w ...
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(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.
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.
Examples
Interval Scheduling Problem
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:
* Begin with an empty set of intervals.
* 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(I)'' be any optimal solution of the interval scheduling problem, and let ''EFT(I)'' be the solution of the earliest finishing time algorithm. For any interval ''J ∈ OPT(I)'', define ''h(J)'' as the interval ''J' ∈ EFT(I)'' that intersects ''J'' with the earliest finishing time amongst all intervals in ''EFT(I)'' 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(I)'' to those in ''EFT(I)''. Suppose ''J'' is an arbitrary interval in ''OPT(I)''.
Show that ''h'' is a function mapping ''OPT(I)'' to ''EFT(I)''.
:Assume for a contradiction that there is no interval ''J' ∈ EFT(I)'' satisfying ''h(J) = J. By definition of ''h'', this means that no interval in ''EFT(I)'' intersects with ''J''. However, this would also mean that ''J'' is compatible with every interval in ''EFT(I)'', and so the earliest finishing time algorithm would have added ''J'' into ''EFT(I)'', and so ''J ∈ EFT(I)''. A contradiction arises, since ''J'' was assumed to not intersect with any interval in ''EFT(I)'', yet ''J'' is in ''EFT(I)'', and ''J'' intersects with itself. Thus by contradiction, ''J'' must intersect with at least one interval in ''EFT(I)''.
:It remains to show that ''h(J)'' is unique. Based on the definition of compatibility, it can never be the case that two compatible intervals have the same finishing time. Since all intervals in ''EFT(I)'' are mutually compatible, none of these intervals have the same finishing time. In particular, every interval in ''EFT(I)'' that intersects with ''J'' have distinct finishing times, and so ''h(J)'' is unique.
Show that ''h'' is one-to-one.
:Assume for a contradiction that ''h'' is not injective. Then there are two distinct intervals in ''OPT(I)'', ''J1'' and ''J2'', such that ''h'' maps both ''J1'' and ''J2'' to the same interval ''J' ∈ EFT(I)''. Without loss of generality, assume that f1 < f2. The intervals ''J1'' and ''J2'' cannot intersect because they are both in the optimal solution, and so f1 ≤ s2< f2. Since ''EFT(I)'' contains ''J' '' instead of ''J1'', the earliest finishing time algorithm encountered ''J' '' before ''J1''. Thus, ''f' ≤ f1''. However, this means that ''f' ≤ f1 ≤ s2< f2'', so ''J' '' and ''J2'' do not intersect. This is a contradiction because ''h'' cannot map ''J2'' to ''J' '' if they do not intersect. Thus by contradiction, ''h'' is injective.
Therefore, ''h'' is a one-to-one function mapping intervals in ''OPT(I)'' to those in ''EFT(I)''. By the charging argument, the earliest finishing time algorithm is optimal.
Job Interval Scheduling Problem
Consider the job interval scheduling problem, an
NP-hard
In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
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 class ''ci''. 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(I)'' and ''EFT(I)'' denote the optimal solution and the solution produced by the earliest finishing time algorithm, as earlier defined. For any interval ''J ∈ OPT(I)'', 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(I)'' to those in ''EFT(I)''. Suppose ''J'' is an arbitrary interval in ''OPT(I)''.
Show that ''h'' is a function mapping ''OPT(I)'' to ''EFT(I)''.
:First, notice that there is either some interval in ''EFT(I)'' with the same job class as ''J'', or there isn't.
:Case 1. Suppose that some interval in ''EFT(I)'' has the same job class as ''J''.
::If there is an interval in ''EFT(I)'' with the same class as ''J'', then ''J'' will map to that interval. Since the intervals in ''EFT(I)'' are mutually compatible, every interval in ''EFT(I)'' must have a different job class. Thus, such an interval is unique.
:Case 2. Suppose that there are no intervals in ''EFT(I)'' with the same job class as ''J''.
::If there are no intervals in ''EFT(I)'' with the same class as ''J'', then ''h'' maps ''J'' to the interval with the earliest finishing time amongst all intervals in EFT(I) intersecting ''J''. The proof of existence and uniqueness of such an interval is given in the previous example.
Show that ''h'' is two-to-one.
:Assume for a contradiction that ''h'' is not two-to-one. Then there are three distinct intervals in ''OPT(I)'', ''J1'', ''J2'', and ''J3'', such that ''h'' maps each of ''J1'', ''J2'', and ''J3'' to the same interval ''J' ∈ EFT(I)''. By the
pigeonhole principle
In mathematics, the pigeonhole principle states that if items are put into containers, with , then at least one container must contain more than one item. For example, if one has three gloves (and none is ambidextrous/reversible), then there mu ...
, at least two of the three intervals were mapped to ''J because they have the same job class as ''J'' ', or because ''J'' ' is the interval with the earliest finishing time amongst all intervals in EFT(I) intersecting both intervals. Without loss of generality, assume that these two intervals are ''J1'' and ''J2''.
:Case 1. Suppose ''J1'' and ''J2'' were mapped to ''J'' ' because they have the same job class as ''J'' '.
::Then each ''J'' ', ''J1'', and ''J2'' have the same job class. This is a contradiction, since the intervals in the optimal solution must be compatible, yet ''J1'' and ''J2'' are not.
:Case 2. Suppose ''J'' ' is the interval with the earliest finishing time amongst all intervals in EFT(I) intersecting both ''J1'' and ''J2''.
::The proof of this case is equivalent to the one in the previous example that showed injectivity. A contradiction follows from the proof above.
Therefore, ''h'' maps no more than two distinct intervals in ''OPT(I)'' to the same interval in ''EFT(I)'', 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.
References
*
Thomas H. Cormen
Thomas H. Cormen is the co-author of ''Introduction to Algorithms'', along with Charles Leiserson, Ron Rivest, and Cliff Stein. In 2013, he published a new book titled '' Algorithms Unlocked''. He is a professor of computer science at Dartmout ...
,
Charles E. Leiserson
Charles Eric Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof. As part of this effort, he developed the Cilk multithreaded language. ...
,
Ronald L. Rivest
Ronald Linn Rivest (; born May 6, 1947) is a cryptographer and an Institute Professor at MIT. He is a member of MIT's Department of Electrical Engineering and Computer Science (EECS) and a member of MIT's Computer Science and Artificial Inte ...
, and
Clifford Stein
Clifford Seth Stein (born December 14, 1965), a computer scientist, is a professor of industrial engineering and operations research at Columbia University in New York, NY, where he also holds an appointment in the Department of Computer Scie ...
. ''
Introduction to Algorithms
''Introduction to Algorithms'' is a book on computer programming by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The book has been widely used as the textbook for algorithms courses at many universities and is co ...
'', Second Edition. MIT Press and McGraw-Hill, 2001.
* Sanjoy Dasgupta,
Christos Papadimitriou
Christos Charilaos Papadimitriou ( el, Χρήστος Χαρίλαος "Χρίστος" Παπαδημητρίου; born August 16, 1949) is a Greek theoretical computer scientist and the Donovan Family Professor of Computer Science at Columbia Un ...
, and
Umesh Vazirani
Umesh Virkumar Vazirani is an Indian-American academic who is the Roger A. Strauch Professor of Electrical Engineering and Computer Science at the University of California, Berkeley, and the director of the Berkeley Quantum Computation Center. Hi ...
. ''
Algorithms
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing c ...
'', First Edition. McGraw-Hill. 2006.
*
Allan Borodin
Allan Bertram Borodin (born 1941) is a Canadian-American computer scientist who is a professor at the University of Toronto.DF document http://www.cs.toronto.edu/~bor/373s11/L2.pdf
*
Allan Borodin
Allan Bertram Borodin (born 1941) is a Canadian-American computer scientist who is a professor at the University of Toronto.DF document http://www.cs.toronto.edu/~bor/373f11/L5-373f11-short.pdf
*
Allan Borodin
Allan Bertram Borodin (born 1941) is a Canadian-American computer scientist who is a professor at the University of Toronto.DF document http://www.cs.toronto.edu/~bor/373s13/L3-actual.pdf
Analysis of algorithms