A greedy-choice property says that some optimal feasible solution contains the locally selected choice. Together with optimal substructure in the remaining instance, it allows repeated commitments. An exchange argument often establishes this property.[ref]
Greedy Algorithms. Algorithms by Jeff Erickson; §4.3 General Pattern, printed pp. 164–165: exchange without worsening an optimum
For interval scheduling, a safe first choice need not belong to every optimal feasible solution. When several optima exist, a commitment may exclude one while retaining another. The useful loop invariant is that the accepted prefix can still be extended to an optimum. Merely keeping the accepted intervals compatible proves feasibility, which is a weaker claim.
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.