Toriodal Instances in 10**7 by 10**7 Square Sample Size = 1,000,000 (for TSP instances up to 1,000 and SUB up to 10,000) OPT - optimal tour length SUB - subtour relaxation lower bound GAP - (OPT - SUB) / SUB (given as a percentage) Mean and Standard Deviation ---------------------------------------------------------------------- ---- 10**6 Samples ----- n OPT Stdev SUB Stdev GAP Stdev ---------------------------------------------------------------------- 10 0.711713 0.063384 0.711233 0.063172 0.065807 0.314404 20 0.713900 0.042726 0.712171 0.042622 0.244144 0.518749 30 0.713651 0.034678 0.711130 0.034667 0.356717 0.524003 40 0.713424 0.029963 0.710402 0.030035 0.427750 0.493877 50 0.713214 0.026745 0.709893 0.026875 0.470179 0.457505 60 0.713143 0.024405 0.709608 0.024565 0.500383 0.424523 70 0.713027 0.022552 0.709348 0.022722 0.520644 0.395557 80 0.712965 0.021100 0.709185 0.021277 0.534875 0.369628 90 0.712914 0.019883 0.709053 0.020068 0.546420 0.348942 100 0.712872 0.018862 0.708947 0.019051 0.555375 0.331065 200 0.712633 0.013324 0.708431 0.013490 0.594177 0.230840 300 0.712562 0.010879 0.708279 0.011024 0.605258 0.186848 400 0.712532 0.009420 0.708213 0.009551 0.610311 0.160873 500 0.712509 0.008428 0.708169 0.008546 0.613170 0.143556 600 0.712482 0.007693 0.708128 0.007802 0.615134 0.130809 700 0.712470 0.007120 0.708106 0.007222 0.616565 0.120809 800 0.712462 0.006658 0.708091 0.006753 0.617533 0.112903 900 0.712453 0.006280 0.708076 0.006370 0.618334 0.106226 1000 0.712448 0.005946 0.708066 0.006032 0.619007 0.100707 2000 0.708024 0.004272 3000 0.708004 0.003484 4000 0.708005 0.003022 5000 0.707994 0.002699 6000 0.707998 0.002464 7000 0.707996 0.002282 8000 0.707989 0.002135 9000 0.707987 0.002015 10000 0.707989 0.001912 ---------------------------------------------------------------------- 100000 (10**3 samples) 0.708000 0.000603 1000000 (10**2 samples) 0.708008 0.000193 ---------------------------------------------------------------------- ---------------------------------------------------------------------- ---- 10**5 Samples ----- n OPT Stdev SUB Stdev GAP Stdev ---------------------------------------------------------------------- 2000 0.712453 0.004213 0.708053 0.004275 0.621545 0.070717 ---------------------------------------------------------------------- The results from Johnson-McGeoch-Rothberg are n m GAP m SUB 100 13957 .5542 98246 .70894 316 1154 .6048 43736 .70818 1000 824 .6124 25000 .70802 3162 14317 .70790 10000 6039 .70794 31622 783 .70791 where the n=1000 GAPs are from ILK runs adjusted downward (based on a sample of 49 instances that were solved with Concorde). The J-M-R estimate for the TSP beta uses the n = 1000 gap in the following way. They estimate the Subtour beta as .70794 (+- .00003) and the subtour value at n = 1000 as 0.70806. From this they conclude that the limit gap should be at most 0.70806 / .70794 = 1.0001695058 or 0.017% above the n = 1000 toroidal gap, giving an over estimate of 0.63 for the limit gap. They take this over estimate as an estimate. The TSP beta estiamte is then at most .70794 * 1.0063 = 0.7124. In a direct attempt to fit a curve to n = 100,316,1000, J-M-R write "one discovers that C_opt,t(N) appears essentially to have converged by N=1000."