Combinatorial optimization tolerances calculated in linear time
Boris I. Goldengorin, Gerard Sierksma · 2003
For a given optimal solution to a combinatorial optimization prob-lem, we show, under very natural conditions, the equality of the min-imal values of upper and lower tolerances, where the upper tolerances are calculated for the given optimal solution and the lower tolerances outside the optimal solution. As a consequence, the calculation of such tolerances can now be done in linear time, while all current methods use quadratic time. 1