An Approximation Algorithm with Factor Two for a Repetitive Routing Problem of Grasp-and-Delivery Robots
Yoshiyuki Karuno*, Hiroshi Nagamochi**,
and Aleksandar Shurbevski*
*Department of Mechanical and System Engineering, Kyoto Institute of Technology, Matsugasaki, Sakyo-ku, Kyoto-shi, Kyoto 606-8585, Japan
**Department of Applied Mathematics and Physics, Kyoto University, Yoshida-honmachi, Sakyo-ku, Kyoto-shi, Kyoto 606-8501, Japan
-  A. Srivastav, H. Schroeter, and C. Michel, “Approximation algorithms for pick-and-place robots,” Annals of Operations Research, Vol.107, pp. 321-338, 2001.
-  M. R. Garey and D. S. Johnson, “Computers and Intractability: A Guide to the Theory of NP-Completeness,” Freeman, 1979.
-  M. S. Krishnamoorthy, “An NP-hard problem in bipartite graphs,” SIGACT News, Vol.7, p. 26, 1975.
-  A. Frank, “A weighted matroid intersection algorithm,” Journal of Algorithms, Vol.2, pp. 328-336, 1981.
-  V. V. Vazirani, “Approximation Algorithms,” Springer, 2001.
-  A. Baltz and A. Srivastav, “Approximation algorithms for the Euclidean bipartite TSP,” Operations Research Letters, Vol.33, pp. 403-410, 2005.
-  J. M. Aldous and R. J. Wilson, “Graphs and Applications: An Introductory Approach,” The Open University, Springer, 2000.
-  P. Chalasani and R. Motwani, “Approximating capacitated routing and delivery problems,” SIAM Journal on Computing, Vol.28, pp. 2133-2149, 1999.
-  B. Korte and J. Vygen, “Combinatorial Optimization: Theory and Algorithms, 3rd Edition,” Springer, 2005.
-  D. S. Johnson and C. H. Papadimitriou, “Performance guarantees for heuristics,” in: E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys (Eds.), “The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization,” Wiley, pp. 145-180, 1985.
-  Y. Karuno, H. Nagamochi, and A. Shurbevski, “Approximation algorithms for a cyclic routing problem of grasp-and-delivery robots,” Proceedings of Joint 5th Int. Conf. on Soft Computing and Intelligent Systems and 11th Int. Symposium on Advanced Intelligent Systems (SCIS & ISIS 2010), pp. 94-99, 2010.
This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.