1
$\begingroup$

I was searching for the $k$-stacker crane problem on google scholar but the best known result is dated back to 1976 with the original paper. I'm unsure whether there would be newer results of the problem, or there are related problem of different names.

Problem description: the 1-SCP problem has a mixed graph and asks for a tour starting from a point $s$ of minimum length so that all arcs are traversed. The $k$-SCP problem is the same but we now need to find k tours so that each arc are traversed at least once, and we want to minimize the maximum tour length.

$\endgroup$
3
  • 1
    $\begingroup$ Did you try following the citations with Google scholar or similar? The paper received more than 600 citations. After a quick browse, I found the following reasonably recent survey, which states in the introduction that it has a section devoted to the SCP: link.springer.com/content/pdf/10.1007/s11750-007-0009-0.pdf (there is also a non-paywalled version via citeseer). Disclaimer: I am entirely new to the SCP. Are you sure your question is research level? I don't know the latest results either, but it may be possible to find it out with the technique described above. $\endgroup$ – Hermann Gruber Apr 15 at 18:59
  • $\begingroup$ And welcome to tcs.SE! $\endgroup$ – Hermann Gruber Apr 15 at 19:01
  • 1
    $\begingroup$ Thanks for replying! After posting I was able to find the paper you linked. The results of SCP they mention (and other newer papers that cite the original) are still the same from 1976. Luckily it seems that another problem, "dial-a-ride" (DAR), which generalizes the capacity of the carrier, is more popular than SCP. But I'm still looking for a work that would improve SCP (i.e. DAR when capacity is 1). It is because right now, the best DAR approx. ratio for a general $k$ is $\min\{\sqrt{n}, \sqrt{k}\}\log ^2n$, which doesn't really help the k=1 case. I will continue looking anyhow. $\endgroup$ – Kien Hunh Apr 15 at 23:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.