Consistent behavior of certain perturbed determinants induced by graphs

We show that the determinant objective function introduced in Ejov et al. [V. Ejov, J. A. Filar, W. Murray, G.T. Nguyen, Determinants and longest cycles of graph, SIAM J. Discrete Math. 22 (33) (2008) 1215–1225] performs well under a certain symmetric linear perturbation. That means sub-graphs corresponding to Hamiltonian cycles of a given graph are maximizers over the hull of all sub-graphs with perturbation parameter ε∈[0,1). Note that in other optimization formulations (see, for example [V.S. Borkar, V. Ejov, J.A. Filar, Directed graphs, Hamiltonicity and doubly stochastic matrices, Random Structures Algorithms 25 (2004) 376–395; V. Ejov, J.A. Filar, M. Nguyen, Hamiltonian cycles and singularly perturbed Markov chains, Math. Oper. Res. 29 (1) (2004) 114–131; J.A. Filar, K. Liu, Hamiltonian cycle problem and singularly perturbed Markov decision process, in: Statistics, Probability and Game Theory: Papers in Honor of David Blackwell, IMS Lecture Notes – Monograph Series, USA, 1996]), ε in the corresponding perturbation was required to be significantly small.