When the greedy algorithm fails
We provide a characterization of the cases when the greedy algorithm may produce the unique worst possible solution for the problem of finding a minimum weight base in a uniform independence system when the weights are taken from a finite range. We apply this theorem to TSP and the minimum bisection problem. The practical message … Read more