<p>I was searching for the <span class="math-container">$k$</span>-stacker crane problem on google scholar but the best known result is dated back to 1976 with the original <a href="https://ieeexplore.ieee.org/abstract/document/4567906?casa_token=aMhm66spep4AAAAA:8QJanUV6iojcDgv4jJR0mE5S_zPRKXs7wkwZVfXkm2H8bL0boH7XMDUL2j9tbFplkuWWsyQMOQ8" rel="nofollow noreferrer">paper</a>. I'm unsure whether there would be newer results of the problem, or there are related problem of different names.</p>
<p>Problem description: the 1-SCP problem has a mixed graph and asks for a tour starting from a point <span class="math-container">$s$</span> of minimum length so that all arcs are traversed. The <span class="math-container">$k$</span>-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.</p>

CC BY-SA 4.0
2021-04-15T18:59:02.877Z
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: https://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.
Hermann Gruber
CC BY-SA 4.0
2021-04-15T19:01:52.193Z
And welcome to tcs.SE!
Hermann Gruber
CC BY-SA 4.0
2021-04-15T23:21:11.620Z
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.
Kien Hunh
<graph-algorithms>
Latest results on the k-stacker crane problem?
Kien Hunh
# Latest results on the k-stacker crane problem?

(Asked by: username_0 on 2021-04-14)

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](https://ieeexplore.ieee.org/abstract/document/4567906?casa_token=aMhm66spep4AAAAA:8QJanUV6iojcDgv4jJR0mE5S_zPRKXs7wkwZVfXkm2H8bL0boH7XMDUL2j9tbFplkuWWsyQMOQ8). 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.

**Tags:** graph-algorithms
> **Comments:**
> **username_1**: 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: https://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.  
> **username_1**: And welcome to tcs.SE!  
> **username_0**: 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.  

---

## 0 answers

