This paper presents an application of topological data analysis (TDA) to discrete optimization problems, which the authors show can improve the performance of the 2-opt local search method for the traveling salesman problem by simply applying standard Vietoris-Rips construction to a data set of trials. They then construct a simplicial complex which is specialized for this sort of simulated data set, determined by a stochastic matrix with a steady state vector (P,π). When P is induced from a random walk on a finite metric space, this complex exhibits similarities with standard constructions such as Vietoris-Rips on the data set, but is not sensitive to outliers, as sparsity is a natural feature of the construction. Authors interpret the persistent homology groups in several examples coming from random walks and discrete optimization, and illustrate how higher dimensional Betti numbers can be used to classify connected components, i.e. zero dimensional features in higher dimensions.
