= Exchange argument
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.<Algorithms by Jeff Erickson/Greedy Algorithms>[Algorithms by Jeff Erickson; §4.3 General Pattern, printed pp. 164–165: exchange at the first disagreement]{ref}
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.
Back to article page
