Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to calculate the time complexity of the $k$-opt algorithm. I started off by first calculating the number of ways of reconnecting the $k$-cycle given that $k$ non-consecutive arcs are removed. The answer is $(k-1)!\,2^{k-1}$.

Next I need to know the number of ways $k$ non-consecutive arcs can be removed in a $k$-cycle. The cycle must be of length $N \ge 2k$. How many ways are there of picking $k$ arcs such that no two arcs are adjacent?

share|improve this question
    
I'm not sure anyone knows what you are talking about. What is $k$-opt? Does this have something to do with graphs, or networks? What kind of graph? How many edges, vertices? What is the purpose of the algorithm? Can you try to meet us halfway? –  Gerry Myerson Apr 24 '12 at 5:46
add comment

1 Answer

When you use terminology from a specialized field (in this case the study of the travelling salesperson problem) in a question, it's usually a good idea to define your terms, at least those whose definition can't immediately be found by searching, and especially those for which, as in this case, a search leads to a different definition than the one you're using.

I take it you're referring to the method of optimizing a TSP solution by removing $k$ non-consecutive arcs and reconnecting the remaining parts of the tour in all possible ways. If so, wherever you have $k$-cycle it should be $N$-cycle; clearly it's impossible to remove $k$ non-consecutive arcs in a $k$-cycle.

Your result $(k-1)!2^{k-1}$ for the first part of the calculation is correct. To find the number of ways of picking $k$ non-consecutive arcs in an $N$-cycle, pick pairs of adjacent arcs instead and then from each pair use the arc that's, say, clockwise from the other. First pick one pair to get from a cycle to a linear chain; then pick $k-1$ pairs in the chain; then correct for the fact that any of the $k$ pairs could have been picked first. That gives $N$ options for the position of the first pair, $\binom{N-k-1}{k-1}$ options for the positions of the remaining pairs, and $k$ options for which pair to pick first, so the result is

$$\frac Nk\binom{N-k-1}{k-1}=\frac{N(N-k-1)!}{k!(N-2k)!}\;.$$

share|improve this answer
add comment

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.