{'fraction_non_alphanumeric': 0.018238993710691823, 'fraction_numerical': 0.0031446540880503146, 'mean_word_length': 4.936567164179104, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Local Search Heuristics for Disjoint Connecting Paths

Kleinberg’s algorithm, for the maximum disjoint connecting paths problem (max DCP) between k terminal pairs, obtains an approximate solution by routing each terminal pair in turn via the shortest path, deleting each shortest path before routing the next terminal pair, until no such path exists. We suggest that the number of terminal pairs routed is dependent on the order in which the terminal pairs are routed. We confirm this assumption by sampling the set of permutations. This assumption motivates our evaluation of the efficacy of four local search methods to search the set of permutations of the terminal pairs, which is tested on a set of problem instances obtained by processing the Canadian Road Network and generating random instances of max DCP for k = 9, 11 and 13. The results obtained confirm that using local search to search the set of permutations of the terminal set does improve on Kleinberg’s algorithm. However, we also conclude that, for the problem instances used, there is limited scope for improvement and the local search methods do not out perform an approach based on sampling the set of permutations of the terminal sets. Hence, we can further conclude that, for the correct representation, simple methods often prove to be very effective. From this work, we learn two principal lessons: the need to identify, understand and confirm the assumptions that underly the expected efficacy of the proposed method; and the need to identify a data set that is able to adequately test the hypothesis in question.