Skip to main content
Share Your Experience: Take the 2024 Developer Survey
7 votes

A Travelling Salesman variant where the next distance depends on distance travelled so far

Without the monotonicity condition, if $f$ is given only by oracle access, then in the worst case you need to query it $\Omega(n!)$ times. Proof sketch: For some sequence of integers $S=[a_1, a_2, \...
Tassle's user avatar
  • 881
5 votes
Accepted

A Travelling Salesman variant where the next distance depends on distance travelled so far

We answer OP's question in the negative. These results are for OP's problem with the monotonicity requirements on $f$ (added in OP's edit after @Tassle's answer, invalidating that answer). Lemma 1. ...
Neal Young's user avatar
  • 10.8k
1 vote

A Travelling Salesman variant where the next distance depends on distance travelled so far

The similarity to Travelling Salesman confused me: the more relevant problem is single-machine scheduling with non-constant job lengths. In particular, this paper surveys many scheduling problems in ...
Erel Segal-Halevi's user avatar
1 vote

Bottom up TSP solution?

"If one takes the 2 nearest neighbors of every node and adds them all up, that is a theoretical minimum." This isn't true. You are adding up 2 edges per vertex, where a TSP solution has one ...
NaturalLogZ's user avatar
1 vote

Generate TSP instances with known optimal

If someone is still searching for this, I might give a gist of how I understood that paper: Generate an optimal permutation $p$ of $\{1...n\}$. Create two random variables, $\alpha_i$ and $\beta_j$, ...
Ferazhu's user avatar
  • 11

Only top scored, non community-wiki answers of a minimum length are eligible