ALGORITHM: Multi-Fragment - Jon Bentley's kd-tree based implementation of Greedy

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
27494385
17.70
18.60
0.13
0.05
--
E1k.1
26316209
14.49
15.22
0.12
0.05
--
E1k.2
26530429
15.23
16.06
0.13
0.05
--
E1k.3
27033547
16.81
17.53
0.13
0.05
--
E1k.4
26467511
16.60
17.41
0.12
0.05
--
E1k.5
26840234
15.73
16.41
0.12
0.05
--
E1k.6
28297348
21.19
22.15
0.12
0.05
--
E1k.7
27637102
20.80
21.93
0.12
0.05
--
E1k.8
26645986
15.72
16.89
0.12
0.05
--
E1k.9
27394231
17.29
18.00
0.12
0.05
--
E3k.0
47391812
16.63
17.46
0.43
0.19
--
E3k.1
47622395
18.12
18.92
0.43
0.19
--
E3k.2
46051871
14.26
15.11
0.44
0.20
--
E3k.3
47777886
17.71
18.50
0.43
0.19
--
E3k.4
47134097
15.65
16.49
0.43
0.19
--
E10k.0
83537327
?
17.06
1.43
0.62
--
E10k.1
83168578
?
16.21
1.43
0.62
--
E10k.2
82758628
?
15.99
1.43
0.62
--
E31k.0
146183206
?
15.58
5.47
1.77
--
E31k.1
145652129
?
15.01
5.51
1.78
--
E100k.0
258083866
?
15.05
22.61
5.09
--
E100k.1
256829082
?
14.53
23.05
5.19
--
E316k.0
456440228
?
14.52
88.20
12.77
--
E1M.0
809348708
?
14.20
329.18
60.35
--
E3M.0
1436837840
?
14.03
1190.57
232.48
--
E10M.0
2553878230
?
14.01
4265.63
930.05
--
C1k.0
13549954
18.99
19.64
0.12
0.05
--
C1k.1
13311373
17.01
17.48
0.12
0.05
--
C1k.2
12644039
16.48
16.98
0.12
0.05
--
C1k.3
13595325
14.38
14.98
0.12
0.05
--
C1k.4
13431002
16.79
17.47
0.13
0.05
--
C1k.5
13623888
19.56
20.26
0.13
0.05
--
C1k.6
12451976
22.48
23.38
0.13
0.05
--
C1k.7
13203805
23.81
24.53
0.12
0.05
--
C1k.8
13537979
16.65
17.05
0.13
0.05
--
C1k.9
13396357
22.82
23.63
0.12
0.05
--
C3k.0
23331536
21.53
22.28
0.43
0.19
--
C3k.1
22648198
19.09
19.82
0.43
0.19
--
C3k.2
24116846
23.38
24.24
0.43
0.19
--
C3k.3
23249611
21.67
22.36
0.43
0.19
--
C3k.4
22738893
20.54
21.23
0.43
0.19
--
C10k.0
39698720
?
21.10
1.39
0.60
--
C10k.1
40625302
?
23.26
1.41
0.61
--
C10k.2
40488062
?
22.96
1.40
0.61
--
C31k.0
72191791
?
22.01
5.35
1.73
--
C31k.1
71657547
?
21.78
5.36
1.74
--
C100k.0
126006582
?
21.26
22.58
5.08
--
C100k.1
127140751
?
21.48
22.61
5.09
--
C316k.0
225312619
?
21.41
86.79
12.56
--
M1k.0
--
--
--
--
--
--
M1k.1
--
--
--
--
--
--
M1k.2
--
--
--
--
--
--
M1k.3
--
--
--
--
--
--
M3k.0
--
--
--
--
--
--
M3k.1
--
--
--
--
--
--
M10k.0
--
--
--
--
--
--
dsj1000
21705226
16.32
17.03
0.12
0.05
--
pr1002
302052
16.60
17.64
0.12
0.05
--
si1032
--
--
--
--
--
--
u1060
--
--
--
--
--
--
vm1084
--
--
--
--
--
--
pcb1173
67296
18.29
19.42
0.14
0.06
--
d1291
--
--
--
--
--
--
rl1304
306224
21.06
22.94
0.15
0.06
--
rl1323
307420
13.78
15.65
0.15
0.06
--
nrw1379
65644
15.90
16.40
0.18
0.08
--
fl1400
--
--
--
--
--
--
u1432
178103
16.43
16.76
0.16
0.07
--
fl1577
--
--
--
--
--
--
d1655
--
--
--
--
--
--
vm1748
--
--
--
--
--
--
u1817
--
--
--
--
--
--
rl1889
377805
19.36
21.21
0.22
0.09
--
d2103
--
--
--
--
--
--
u2152
--
--
--
--
--
--
u2319
265389
13.29
13.31
0.25
0.11
--
pr2392
457661
21.06
22.54
0.30
0.13
--
pcb3038
162683
18.15
19.11
0.40
0.18
--
fl3795
--
--
--
--
--
--
fnl4461
214295
17.38
18.02
0.60
0.27
--
rl5915
633855
12.08
13.83
0.71
0.32
--
rl5934
651519
17.17
18.79
0.72
0.32
--
pla7397
27259144
17.19
17.87
0.88
0.39
--
rl11849
--
--
--
--
--
--
usa13509
--
--
--
--
--
--
brd14051
541628
15.39
15.95
2.10
0.87
--
d15112
1819922
15.69
16.30
2.38
0.97
--
d18512
744674
15.41
15.97
2.80
1.09
--
pla33810
76295322
15.51
16.12
4.43
1.42
--
pla85900
162992015
14.49
14.94
12.24
3.00
--