a variation on the traveling salesmen problem

[futurebird]

I’m thinking about a variation of the traveling salesmen problem called the Euclidean traveling salesmen problem. In it the distances between the cities are a set of straight, coplanar lines. I’m also only concerned with a set of complete cities (so there is a road between every city

Comments

[fallenicarus]

let n be the number of vertices, and e_n the number of edges for veritces n, c_n be the number of checks... and let n be a natural number, of course

so e_n = e_(n-1) + (n-1)

and c_n = e_n - n + 1

if you write them in terms of their formulas.. which i haven't proven, but it's readily observed that they work, you can see that the progression is similar but not exact. so the fact that it doesn't start out the same way shouldn't give you any trouble.. because checks are dependent upon vertices and edges, and edges are clearly dependent upon vertices.