An alternative solution to the problem is to treat it as a set of potentially
inconsistent constraints:

(7) |

Let .

Consider the difference in cost between
and
. The cost
difference is:

(8) |

Since, by definition of rounding, , then for both cases, confirming that is (locally) the best solution.

The smallest cost difference is:

(9) |

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:

(10) |

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:

(11) | |||

(12) |

From these, calculate , and then and then repeat the selection process to choose a new pair of regions to merge.

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.