An exchange argument modifies an optimal feasible solution to include a desired choice while preserving feasibility and not worsening its objective function value. The modification need not strictly improve the optimum; equality suffices.[ref]
Greedy Algorithms. Algorithms by Jeff Erickson; §4.3 General Pattern, printed pp. 164–165: exchange at the first disagreement
For interval scheduling, the exchange replaces the first selected job with an earliest-finishing job. Its safety comes from the finish-time inequality below. Replacing a job with a shorter one has no such guarantee: it might move the occupied interval into the middle of two useful jobs, as the shortest-duration interval scheduling counterexample shows.
Articles by others on the same topic
There are currently no matching articles.