# A New Constructive Heuristic Driven by Machine Learning for the Traveling Salesman Problem
## Appendix A Complexity of the Inner-Loop Constraint Tracker  
The purpose here is to compute the complexity of the inner-loop constraint tracker used in the _ML-Constructive_ heuristic process, as stated in Section 2.4 and in Algorithm 1. For comprehension purposes we strict our analysis to the symmetric TSP, but similar results can be achieved for the asymmetric case as well. Firstly, we observe that the constraint tracker procedure is applied only to edges that have both extremes with exactly one connection already in the partial solution, since the tracker routine follows the constraints expressed by lines 8 and 22 in Algorithm 1. Therefore, edges connecting vertices from internal points of the fragments are impossible to occur at this point, as shown in Figure 11. While those creating an inner-loop and joining two fragments are possible to occur events (Figure 11). Note that the goal of the tracker is to detect the inner-loop connections from the other. The growing connections and new fragment connections shown in Figure 11 are events that can be detected in constant time, since it's enough to check that an extreme of the inserting edge has zero connections in the partial solution (lines 12 and 25). Also, note that these two events cannot occur as input of the tracker procedure since they do not satisfy the constraint expressed by lines 8 and 22. Secondly, we notice that the complexity of the worst-case scenario for the whole procedure (from empty solution to the complete) is being computed in this Appendix. Therefore, we are not taking into consideration just the single call of the tracker, but the global computation during the complete tracking process. In fact, considering that the maximum number of positive addition for a constructive heuristic that grows fragments is equal to \(n\) (the length of the tour). Where, an addition is positive if the edge being attached to the partial solution complies with the TSP constraints in (1b-e) and the ML decision-taker agrees to add the considered edge in solution. We refer to the epoch between two positive additions as \(t\), e.g., no edge is in solution at \(t=0\), meanwhile exactly eight edges are in solution at \(t=8\). Take into consideration that the epochs to be checked by the tracking routine for the symmetric TSP are from \(t=2\) to \(t=n-2\). As mentioned, the computationally expensive events that the tracker needs to check are the \"inner-loop connection\" and the \"joining fragments connections\". The inner-loop connection drawn in yellow (Figure 11) occurs when the extremes of a fragment are connected together by the attaching edge \(l\). If we assume that at the epoch \(t\) there are at most \(s\leq t\) fragments, then there exist at most \(s\) attaching edges at this epoch that can create an inner loop (Figure 12), and the sum of the operation needed to check these \(s\) inner-loops is at most equal to \(t\). In fact, the tracker checks by spanning completely one of the fragments connecting to the attaching edge. Then if the other extreme of the fragment coincides with the other extreme of the attaching edge there is an \"inner loop connection\", otherwise there is a \"joining fragments connection\". Note that once an edge has been rejected the fragment associated with it is set free for the current epoch, and the tracker does not need to check anymore its extremes. Since we have at most \(t\) operations for epoch, and we have at most \(n\) epochs, the global computation is \(O(n^{2})\). Once the upper bound of the complexity for detecting the \"inner-loop connections\" has been found, the number of operations required for the \"joining fragments connections\" occurrences is still necessary to be estimated. Usually, after having encountered a \"joining fragments connection\" event, the insertion of the considered edge \(l\) takes place. But since in _ML-Constructive_ it could happen that the ML decision-taker rejects the attaching edge (line 10), it may happen that the tracker is called many times during the same epoch.