Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Are there deterministic algorithms that generate a sequence of Hamilton Tours that is superior to a sequence of randomly chosen tours, when applied to the TSP (by applying to the TSP, I understand summing up a tour's edge weights)?

Whether Low Discrepancy is better that Random Generation is decided via the index of the Optimal Tour in the Low Discrepancy sequence of all tours.
If it is more likely to encounter the Optimal Tour in the Low Discrepancy sequence earlier than in the Random Generation sequence, then Low Discrepancy is conidered superior.
That measure of superiority is only one concrete example; other ways of defining it are also possible, while eventually yielding a different decision.

Background of my question is to learn whether similar improvements as in multidimensional integration are possible when switching from Monte Carlo to Low Discrepancy.
Note however, that multidimensional integration only serves as an example for the beneficial use of Low Discrepancy but is otherwise considered as being completely unrelated to TSP

I also appreciate any further information as well, like how to define a discrepancy measure for tours, estimates for performance gains, etc.

I know that there are methods for generating Low Discrepancy permutations, but I want information dedicated to tours and not to permutations in general.

What I have tried so far, is to combine the ability to calculate the n-th permutation via factoradic numbers with n taken from an appropriately chosen van der Corput sequence. I'm not quite satisfied with that approach because:
-the calculation of the n-th permutation is based on lexicographical ordering but, I would prefer the order generated by the Steinhaus-Trotter algorithm (because of the minimal change from one permutation to the next)
-the van der Corput sequence corresponds to inverting the sequence of bits and is thus tailored for value ranges that are powers of two; numbers ranges that are factorials do not fit that pattern and one has to reject certain values of the van der Corput sequence because they are outside the valid range
-cyclicity and symmetry are not taken into account

all that adds some bias, which worries me

share|cite|improve this question
Superior in what sense? Also I don't see the analogy as integration is summing/averaging and TSP is minimizing. –  Brendan McKay Jul 27 '13 at 16:21
@Brendan: by superior I mean that the minimum of the first k generated tours is smaller on the average. There is of course no relation to integration; that only was intended as an example for beneficial use of Low Discrepancy methods. –  Manfred Weis Jul 27 '13 at 16:56
Ok, that is an interesting question but I suggest you edit the text to add this information. Nobody will respond if they don't get it. –  Brendan McKay Jul 28 '13 at 1:51
@BrendanMcKay: I edited my problem description in response to your feeback; thanks for the input. –  Manfred Weis Jul 28 '13 at 10:23

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.