Greedy heuristics with regret, with application to the cheapest insertion algorithm for the TSP

We consider greedy algorithms that allow partial regret. As an example we consider a variant of the cheapest insertion algorithm for the TSP. Our numerical study indicates that in most cases it significantly reduces the relative error, and the added computational time is quite small.