Non-approximability of the single crane container transhipment problem

References

• Aggarwal, N., N. Garg, and S. Gupta. 2011. “A 43-Approximation for TSP on Cubic 3-Edge-Connected Graphs.” ArXiv:1101.5586.
   Google Scholar
• Arora, S. 1996. “Polynomial Time Approximation Schemes for Euclidean TSP and Other Geometric Problems.” Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 2–11. IEEE.
   Google Scholar
• Asadpour, A., M. X. Goemans, A. Mdry, S. O. Gharan, and A. Saberi. 2017. “An O(log⁡n/loglog⁡n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem.” Operations Research 65: 1043–1061. doi: 10.1287/opre.2017.1603
   Google Scholar
• Barketau, M., and E. Pesch. 2016. “An Approximation Algorithm for a Special Case of the Asymmetric Travelling Salesman Problem.” International Journal of Production Research 54: 4205–4212. doi: 10.1080/00207543.2015.1113327
   Web of Science ®Google Scholar
• Barketau, M., E. Pesch, and Y. Shafransky. 2015. “Minimizing Maximum Weight of Subsets of a Maximum Matching in a Bipartite Graph.” Discrete Applied Mathematics 196: 4–19. doi: 10.1016/j.dam.2015.01.008
   Web of Science ®Google Scholar
• Boyd, S., R. Sitters, S. van der Ster, and L. Stougie. 2011. “TSP on Cubic and Subcubic Graphs.” IPCO, 65–77.
   Google Scholar
• Boysen, N., M. Fliedner, F. Jaehn, and E. Pesch. 2012. “A Survey on Container Processing in Railway Yards.” Transportation Science 47: 312–329. doi: 10.1287/trsc.1120.0415
   Web of Science ®Google Scholar
• Boysen, N., and K. Stephan. 2016. “A Survey on Single Crane Scheduling in Automated Storage/Retrieval Systems.” European Journal of Operational Research 254: 691–704. doi: 10.1016/j.ejor.2016.04.008
   Web of Science ®Google Scholar
• Christofides, N. 1976. “Worst-case Analysis of a New Heuristic for the Traveling Salesman Problem.” Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh.
   Google Scholar
• Frieze, A. M., G. Galbiati, and F. Maffioli. 1982. “On the Worst-case Performance of Some Algorithms for the Asymmetric Traveling Salesman Problem.” Networks 12: 23–39. doi: 10.1002/net.3230120103
   Web of Science ®Google Scholar
• Gamarnik, D., M. Lewenstein, and M. Sviridenko. 2005. “An Improved Upper Bound for the TSP in Cubic 3-Edge-Connected Graphs.” Operations Research Letters 33: 467–474. doi: 10.1016/j.orl.2004.09.005
   Web of Science ®Google Scholar
• Garey, M. R., and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: Freeman and Company.
   Google Scholar
• Kress, D., S. Meiswinkel, and E. Pesch. 2019. “Straddle Carrier Routing at Seaport Container Terminals in the Presence of Short Term Quay Crane Buffer Areas. European Journal of Operational Research (to appear).
   Web of Science ®Google Scholar
• Kuzmicz, K. A., and E. Pesch. 2017. “Prerequisites for the Modelling of Empty Container Supply Chains.” Engineering Management in Production and Services 9: 28–36. doi: 10.1515/emj-2017-0023
   Google Scholar
• Kuzmicz, K. A., and E. Pesch. 2019. “Approaches to Empty Container Repositioning Problems in the Context of Eurasian Intermodal Transportation.” Omega 85: 194–213. doi: 10.1016/j.omega.2018.06.004
   Web of Science ®Google Scholar
• Li, X., A. Otto, and E. Pesch. 2019. “Solving the Single Crane Scheduling Problem at Rail Transshipment Yards.” Discrete Applied Mathematics 264: 134–147. doi: 10.1016/j.dam.2018.07.021
   Web of Science ®Google Scholar
• Mömke, T., and O. Svensson. 2016. “Removing and Adding Edges for the Traveling Salesman Problem.” Journal of the ACM 63 (1): 2:1–2:28. doi: 10.1145/2739008
   Web of Science ®Google Scholar
• Mucha, M. 2014. “139-Approximation for Graphic GSP.” Theory of Computing Systems 55: 640–657. doi: 10.1007/s00224-012-9439-7
   Google Scholar
• Nossack, J., D. Briskorn, and E. Pesch. 2018. “Container Dispatching and Conflict-free Yard Crane Routing in an Automated Container Terminal.” Transportation Science 52: 1059–1076. doi: 10.1287/trsc.2017.0811
   Web of Science ®Google Scholar
• Otto, A., N. Agatz, J. Campbell, B. Golden, and E. Pesch. 2018. “Optimization Approaches for Civil Applications of Unmanned Aerial Vehicles (UAVs) or Aerial Drones: A Survey.” Networks 72: 411–458. doi: 10.1002/net.21818
   Web of Science ®Google Scholar
• Otto, A., X. Li, and E. Pesch. 2017. “Two-way Bounded Dynamic Programming Approach for Operations Planning in Transshipment Yards.” Transportation Science 51: 325–342. doi: 10.1287/trsc.2016.0688
   Web of Science ®Google Scholar
• Oveis Gharan, S., A. Saberi, and M. Singh. 2011. “A Randomized Rounding Approach to the Traveling Salesman Problem.” Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 550–559.
   Google Scholar
• Papadimitriou, C. H., and S. Vempala. 2006. “On the Approximability of the Traveling Salesman Problem.” Combinatorica 26: 101–120. doi: 10.1007/s00493-006-0008-z
   Web of Science ®Google Scholar
• Sebõ, A. 2013. “Eight-fifth Approximation for the Path TSP.” In M. Goemans and J. Correa (eds.) Integer Programming and Combinatorial Optimization, 362–374. Berlin, Heidelberg: Springer.
   Google Scholar
• Sebõ, A., and J. Vygen. 2012. “Shorter Tours by Nicer Ears.” ArXiv:1201.1870.
   Google Scholar
• Stahlbock, R., and S. Voss. 2008. “Operations Research at Container Terminals: A Literature Update.” OR Spectrum 30: 1–52. doi: 10.1007/s00291-007-0100-9
   Web of Science ®Google Scholar
• Svensson, O., J. Tarnawski, and L. A. Vegh. 2017. “A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem.” ArXiv:1708.04215.
   Google Scholar
• Vishnoi, N. K. 2012. “A Permanent Approach to the Traveling Salesman Problem.” 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS), 76–80.
   Google Scholar
• Vygen, J. 2012. “New Approximation Algorithms for the TSP.” Forschungsinstitut für Diskrete Mathematik, Rheinische Friedrich-Wilhelms-Universität Bonn. http://www.or.uni-bonn.de/home/vygen/files/optima.pdf.
   Google Scholar
• Zenklusen, R. 2018. “A 12-approximation for Path TSP.” ArXiv:1805.04131.
   Google Scholar