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) |
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.