New answers tagged

3 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
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
6 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
  • 861

Top 50 recent answers are included