ALGORITHM: Spacefilling-Curve algorithm of Bartholdi and Platzman

MACHINE: Silicon Graphics 196 Mhz MIPS R10000 [ mips196 ]

RUN: 1

SUBMITTER: Johnson-McGeoch

Instance
Tour Length
Percent over OPT
Percent over HK
Running Time (Seconds)
Normalized Time
Memory Usage (Megabytes)
E1k.0
30424830
30.24
31.24
0.01
0.00
--
E1k.1
29863068
29.92
30.75
0.01
0.00
--
E1k.2
30350220
31.82
32.77
0.01
0.00
--
E1k.3
30820145
33.17
33.99
0.01
0.00
--
E1k.4
30131330
32.74
33.66
0.01
0.00
--
E1k.5
30185724
30.15
30.92
0.01
0.00
--
E1k.6
30757623
31.73
32.77
0.01
0.00
--
E1k.7
30354158
32.67
33.91
0.01
0.00
--
E1k.8
29825134
29.53
30.84
0.01
0.00
--
E1k.9
30553539
30.82
31.61
0.01
0.00
--
E3k.0
53740548
32.25
33.19
0.03
0.01
--
E3k.1
53502923
32.71
33.60
0.03
0.01
--
E3k.2
53630242
33.07
34.05
0.03
0.01
--
E3k.3
53473710
31.74
32.63
0.03
0.01
--
E3k.4
54034655
32.58
33.54
0.03
0.01
--
E10k.0
96409189
?
35.10
0.10
0.04
--
E10k.1
96021655
?
34.17
0.10
0.04
--
E10k.2
95893376
?
34.40
0.10
0.04
--
E31k.0
170396691
?
34.73
0.33
0.11
--
E31k.1
170581478
?
34.69
0.33
0.11
--
E100k.0
302843488
?
35.00
1.08
0.24
--
E100k.1
302459062
?
34.88
1.07
0.24
--
E316k.0
538105998
?
35.00
4.39
0.64
--
E1M.0
957366726
?
35.09
16.30
2.99
--
E3M.0
1701766891
?
35.06
54.39
10.62
--
E10M.0
3025758032
?
35.08
177.07
38.61
--
C1k.0
15732653
38.16
38.91
0.01
0.00
--
C1k.1
15714617
38.13
38.69
0.01
0.00
--
C1k.2
15138224
39.46
40.05
0.01
0.00
--
C1k.3
16148720
35.86
36.58
0.01
0.00
--
C1k.4
15888853
38.16
38.96
0.01
0.00
--
C1k.5
16487520
44.69
45.54
0.01
0.00
--
C1k.6
14512942
42.75
43.80
0.01
0.00
--
C1k.7
15174951
42.29
43.12
0.01
0.00
--
C1k.8
16219306
39.75
40.23
0.01
0.00
--
C1k.9
15698355
43.93
44.87
0.01
0.00
--
C3k.0
27286423
42.13
43.01
0.03
0.01
--
C3k.1
27944258
46.94
47.84
0.03
0.01
--
C3k.2
42662312
118.25
119.78
0.03
0.01
--
C3k.3
27800126
45.49
46.31
0.03
0.01
--
C3k.4
27525729
45.92
46.74
0.03
0.01
--
C10k.0
49379765
?
50.63
0.10
0.04
--
C10k.1
71777890
?
117.78
0.10
0.04
--
C10k.2
49431597
?
50.13
0.10
0.04
--
C31k.0
89235802
?
50.81
0.33
0.11
--
C31k.1
141307184
?
140.15
0.33
0.11
--
C100k.0
180856433
?
74.04
1.07
0.24
--
C100k.1
187951836
?
79.58
1.08
0.24
--
C316k.0
281490772
?
51.68
4.25
0.62
--
M1k.0
--
--
--
--
--
--
M1k.1
--
--
--
--
--
--
M1k.2
--
--
--
--
--
--
M1k.3
--
--
--
--
--
--
M3k.0
--
--
--
--
--
--
M3k.1
--
--
--
--
--
--
M10k.0
--
--
--
--
--
--
dsj1000
132763050
611.48
615.82
0.01
0.00
--
pr1002
364559
40.73
41.98
0.01
0.00
--
si1032
--
--
--
--
--
--
u1060
--
--
--
--
--
--
vm1084
--
--
--
--
--
--
pcb1173
80189
40.95
42.30
0.01
0.00
--
d1291
--
--
--
--
--
--
rl1304
413582
63.50
66.03
0.01
0.00
--
rl1323
438287
62.21
64.88
0.01
0.00
--
nrw1379
73942
30.55
31.11
0.01
0.00
--
fl1400
--
--
--
--
--
--
u1432
197508
29.12
29.48
0.01
0.00
--
fl1577
--
--
--
--
--
--
d1655
--
--
--
--
--
--
vm1748
--
--
--
--
--
--
u1817
--
--
--
--
--
--
rl1889
517608
63.52
66.06
0.02
0.01
--
d2103
--
--
--
--
--
--
u2152
--
--
--
--
--
--
u2319
264225
12.79
12.81
0.02
0.01
--
pr2392
545731
44.36
46.12
0.02
0.01
--
pcb3038
193520
40.54
41.68
0.02
0.01
--
fl3795
--
--
--
--
--
--
fnl4461
241518
32.29
33.02
0.04
0.02
--
rl5915
905887
60.18
62.68
0.05
0.02
--
rl5934
887522
59.61
61.82
0.05
0.02
--
pla7397
32370616
39.16
39.97
0.07
0.03
--
rl11849
--
--
--
--
--
--
usa13509
--
--
--
--
--
--
brd14051
617006
31.45
32.09
0.13
0.05
--
d15112
2077295
32.05
32.74
0.15
0.06
--
d18512
841997
30.50
31.13
0.18
0.07
--
pla33810
92627525
40.24
40.97
0.35
0.11
--
pla85900
194834192
36.86
37.39
0.93
0.23
--