An alternative solution to the problem is to treat it as a set of potentially
Consider the difference in cost between
. The cost
Since, by definition of rounding, , then for both cases, confirming that is (locally) the best solution.
The smallest cost difference is:
Choose the interface where this cost difference is the largest. That is, choose the pair of regions where getting the offset ``wrong'' is the most disastrous.
Therefore, select the pair of regions according to:
Once this pair is selected, merge them into a new, single region using
the ``optimal'' offset .
Update the statistics for all interfaces to this new region. That is, for
all regions , the new statistics are:
Keep merging regions until there are no more interfaces between regions (usually when only one region remains if there is a single connected set of regions initially).
As each iteration of this algorithm merges two regions, the number of iterations required is . Within each iteration a search for the maximum value must take place, followed by the updating or deletion of all constraints related to the two selected regions.