6.5 Comparison of CA, CA1, and CA2
The best found results for the heuristics are reported in Tables 6.4 and 6.5.
Table 6.6: Comparison of the performance of CA, CA1, andCA2.
CA CA1 CA2 Number of times heuristic is
best or tied for best 1 23 50
Average rank 2.96 1.54 1
Mimimum ratio of worst found
solution and optimal or best known 0.45 0.61 0.65
Maximum range 6 12 16
The solution quality difference of the fast algorithms is clear. CA1, and CA2find quite similar solutions, and they outperformCAwith a clear margin.
For all 50 test instances, algorithmCA2finds the best solution, andCA1finds the same solution asCA2for 23 graphs. The solutions ofCAare always worse than the those of CA1 and CA2 for graphs that contain triangles. The only graph for which all the algorithms found the same solution was cimi-g6. The average rank of the heuristics is 2.96 for CA, 1.54 for CA1, and 1 for CA2.
The comparison statistics are collected in Table 6.6.
Figure 6.6 shows the average running times of one run for CA, CA1, and CA2 as a function of the number of edges. Further, the figure contains the average running time of GRE to illustrate the running time difference of the greedy heuristics and heuristics without planarity test. The running times of CA and CA1 are less than one second for all graphs up to 50000 edges and for graph r1 having 49950 edges CA2 took on average 1.3 seconds. For the largest graph, r9 with 449550 edges, the average running times were 4.2, 5.8, and 6.5 seconds, respectively.
The running time differences between CA, CA1, and CA2 is in general very small. Only with the graphs having more than 10000 edges it can be seen that CA is slightly faster than the other two algorithms. CA2 is the slowest method. The sharp turns in the curve are the influence of the number of vertices. All three heuristics run faster for a sparse graph than for a dense graph with the same number of edges.
The variation of the solutions of all three algorithms is quite small. Figure 6.7 illustrates differences of the best found solution and the worst found solu-tion of the heuristics for graphs with less than 1600 edges. The variasolu-tion of the solutions of CAwas very small, the worst case difference of the worst and best
0.001
Average running time in seconds
Edges
Average running time in seconds
Edges
Average running time in seconds
Edges
Average running time in seconds
Edges CA2
Figure 6.6: Average running times of CA,CA1, CA2, andGRE. Notice that the axes are logarithmic.
0
0 200 400 600 800 1000 1200 1400 1600
Range
0 200 400 600 800 1000 1200 1400 1600
Range
0 200 400 600 800 1000 1200 1400 1600
Range
Edges CA2
Figure 6.7: Ranges of the solutions of CA,CA1, and CA2.
solutions found solutions were at most 6 edges (tg200.9). The ranges of the solutions of CA1and CA2were at most 12 (g19), and 16 (g19), respectively.
See Table 6.6 for these results. For the largest graphs, r0, r1, r9, and crack, the ranges were higher, up to 138 for crack by CA2. See Appendix A for the best and worst solutions of CA, CA1, and CA2for graphs having over 1600 edges.
To further compare the solutions of CA2andCA, we studied their solution quality difference. See Figure 6.8 for the ratios of the best found solutions of CA2 and CA and Figure 6.9 for the ratios of the worst found solutions of CA2 and the best found solutions of CA. The figures are very similar, since the solution qualities of CA2 and CA do not vary much. The highest
6.5. COMPARISON OF CA, CA1, AND CA2
0 200 400 600 800 1000 1200 1400 1600
Best CA2 vs. Best CA
0 200 400 600 800 1000 1200 1400 1600
Best CA2 vs. Best CA
Edges
Figure 6.8: Ratios of the best found solutions of CA2and CA.
0.9
0 200 400 600 800 1000 1200 1400 1600
Worst CA2 vs. Best CA
0 200 400 600 800 1000 1200 1400 1600
Worst CA2 vs. Best CA
Edges
Figure 6.9: Ratios of the worst found solutions of CA2 and the best found solutions of CA.
improvement was for tg200.1 with a 1.44 times better solution. In general, the highest improvements were obtained for graphs containing a planar subgraph of maximum size (tg100.1 – tg200.9). The solutions of CA2were approximately 20 percentages better than those of CA.
CA was the first approximation algorithm for MPS with a nontrivial per-formance ratio 7/18, as discussed in Chapter 5. Our experiments verify this theoretical worst case solution ratio. The worst case ratio of CAsolutions and the optimal or the best known solution was always more than 7/18 (the best known solutions are mainly taken from the experiments for SACA1 described in Section 6.7 and in [109]). This is illustrated in Figure 6.10.
Theorems 5.11 and 5.13 show that the performance ratios of CA1andCA2 are at least the same as the performance ratio of CA. Our experiments also verify this, and in addition, the experiments also give evidence on the conjec-tured performance ratio 4/9: the solutions by CA1and CA2were never more than 4/9 away from the optima. For the ratios of the worst found solutions and the optimal or lower bound for CA2, see Figure 6.11.
Also, the worst solutions byCA1andCA2were always as good as the best solution by CA, as illustrated in Figure 6.9 for CA2. The solutions of CA1
0.3
0 200 400 600 800 1000 1200 1400 1600
Performance ratio of CA
Edges
0 200 400 600 800 1000 1200 1400 1600
Performance ratio of CA
Edges
0 200 400 600 800 1000 1200 1400 1600
Performance ratio of CA
Edges
0 200 400 600 800 1000 1200 1400 1600
Performance ratio of CA
Edges
0 200 400 600 800 1000 1200 1400 1600
Performance ratio of CA
Edges Best known solution
Figure 6.10: Ratios of the worst found solutions of CAand the optimal or the best known solution.
0 200 400 600 800 1000 1200 1400 1600
Performance ratio of CA2
Edges
0 200 400 600 800 1000 1200 1400 1600
Performance ratio of CA2
Edges
0 200 400 600 800 1000 1200 1400 1600
Performance ratio of CA2
Edges
0 200 400 600 800 1000 1200 1400 1600
Performance ratio of CA2
Edges
0 200 400 600 800 1000 1200 1400 1600
Performance ratio of CA2
Edges Best known solution
Figure 6.11: Ratios of the worst found solutions of CA2 and the optimal or the best known solution.
and CA2were never less than 0.61 and 0.65 times the optima, respectively.
Table 6.6 lists the minimum of the worst case ratios of the worst found solutions and the optimal or the best known solutions for the heuristics. CA achieved the worst solutions for graph tg200.1, CA1 for graph tg200.5, and CA2for graph tg100.9.