The apportionment paradox article seems to suggest a politically expedient way to avoid paradoxes and obey the quota rule. The best method would be to take the current number of seats and test to see if that number provides a match to the sum of seats based on the required rounding rule. If it does not, apportion a number of seats equal to the nearest number above the current number which provides a match.
Using the 2000 census and the Huntington-Hill method the House would have 436 seats with that rule. Think of the money saved in Utah since they wouldn't have had to sue to try to get an extra seat.
I had thought of a similar method, so I was interested that someone with a stronger mathematical background would come to the same conclusion.
I'm not sure that you should always apportion a number of representatives greater than or equal to the nominal number. Imagine a case where the apportionment using independent rounding did yield a 435 member house, but there was one state, Unlucky, that was just short of the rounding threshold.
Now shift population from one state, Rusty, that was just above the rounding threshold, so that it is somewhat below the rounding threshold, to another state, Sunny, that was also above the threshold (the shift will be small enough that Sunny wll will have the same number of whole representatives, but large enough so that Unlucky is much closer to rounding threshold than Rusty.
So we apply our apportionment based on 435, and discover that we will only have 434 representatives. So we try 436 and Unlucky now gets an additional representative but the total number is only 435. So let's try 437, and now Rusty gets its representative back for a total of 437.
It seems odd that Unlucky should get an additional representative, albeit in a slightly larger body, even though its share of the total population remained the same. There would also be a ratcheting effect on the overall size of the house, since if we didn't start at 437, the next apportionment could cause more losses than gains, which was why we didn't accept the apportionment of 434 members in the first place.
If we just accept that certain states share of the total population didn't warrant an additional representative, then we could start from 435, and end up with a house likely to be within a member or 2 of 435, either way. It should average close to 435 - there may be a slight upward bias due to a few small states (WY, ND, VT) permanently being rounded upward. They will sometime be joined by SD.
So in 2000, instead of having decided whether NC or UT got the 435th seat, would have been to take away NC's 435th seat, and CA's 434th seat.
I did my application of Huntington-Hill in a slightly different manner. Rather than using the quota (state-population/national-average) and rounding using modified thresholds (sqrt1*2), sqrt(2*3), etc.); I calculated a quota as:
sqrt ( (state-population^2/national-average^2) +1/4 )
And then used conventional rounding (fractions over 1/2 round upward)
If you sum these quotas, they come out to 436.84 which reflects the slight small state bias of Huntington-Hill. In Bogomolny's article, if you compare the average value of S-N for values of N in the range 425 to 445, the average for Webster is -0.57, and for Huntington-Hill 0.33.
I would assume that over time, the fractional portion of the state quotas under Webster would be close to uniformally distributed between 0 and 1, and that S-N would average around 0 under Webster, and average 1.84 for Huntington-Hill (assuming little overall change in the distribution of population among large and small states).
I also adjusted the "average" used in Huntington-Hill so that the sum of quotas is 435 (this was done recursively, but convergence is very fast). In the range around 435, this will increase slightly the chance of having a smaller house (S-N is negative). But this may only be a random phenomena. If you go further out to N=415 or N=455, S-N is positive, sometimes as much as +3.