We now focus on making a decision as quickly as possible. Most of the time required to make the decision is spent computing the features that the classifiers need. We removed the most expensive features - all the properties of the primal graph described in Section 4 apart from edge density.

The results for the reduced set of features are shown in Table 2 as well. The performance is not significantly worse and even better on the first set of instances, but the time required to compute all the features is only about 3 seconds per instance. On the first set of benchmarks, we solve each instance on average 8 seconds faster using our system (misclassification penalty of default decision minus that of our system divided by the number of instances in the set). We are therefore left with a performance improvement of an average of 5 seconds per instance. On the second set, we cannot reasonably expect a performance improvement - the perfect oracle classifier only achieves about 0.2 seconds per instance on average.

![0_image_0.png](0_image_0.png)

Figure 2 revisits Figure 1 and shows the actual speedup our meta-classifier achieves for each instance. It convincingly illustrates the quality of our classifier.

The instances where we suffer a slowdown are ones that are solved almost instantaneously, whereas the correctly classified instances are the hard ones that we care about most. In particular the instances where a large speedup can be gained are classified correctly by our system.