No label defined (Q3972019)

[For the entire collection see Zbl 0698.00017.] For some practical applications (see [(*) \textit{G. Ehnert}, \textit{J. Harant} and \textit{H. Walther}, Teubner-Texte Math. 73, 31-35 (1985; Zbl 0599.90082)]) a problem is interesting which is illustrated in a not necessarily physically correct way as follows: Suppose an organization for time travels wants to carry out some trips into the past. The points of time visited are \(x_ 1,x_ 2,\dots,x_ f\), where \(x_ 1< x_ 2<\cdots <x_ f\). In order to execute these trips there are time travellers in \(r\) stations \(s_ 1,s_ 2,\dots,s_ r\) (their number is not limited in any station). But only the station can take a traveller into the past. A traveller at point \(x_ i\) can jump only in the forward direction, that means jumping to a point \(x_ j\) is possible only if \(x_ i< x_ j\) (which means \(i< j\)) or he can return to his station into the present time. Taking a traveller from station \(s_ k\) to point \(x_ i\) needs \(c^ k_{0i}\) energy units, jumping from \(x_ i\) to \(x_ j\) a traveller needs \(c_{ij}\) energy units and jumping from \(x_ i\) to \(s_ k\) he needs \(c^ k_{i0}\) units. We want to find a set of time travels such that every point \(x_ i\) is visited exactly once and such that the amount of energy is as small as possible. In (*) it was shown that this problem can be solved by a polynomial algorithm if \(r=1\). We show that it is NP-hard if \(r=2\).