|
|||||
|
|
How to collect balls moving in the Euclidean plane |
|
| Authors: | Yuichi Asahiro Toshinori Sakuma |
| Affiliation: | a Department of Social Information Systems, Faculty of Information Science, Kyushu Sangyo University. 2-3-1 Matsukadai, Higashi-ku, Fukuoka 813-8503, Japan b Department of Communications and Computer Engineering, Graduate School of Informatics, Kyoto University, Kyoto 606-8501, Japan c Department of Mathematical Informatics, Graduate School of Information and Technology, University of Tokyo, Tokyo 113-8656, Japan d Department of Computer Science and Communication Engineering, Graduate School of Information Science and Electrical Engineering, Kyushu University, Fukuoka 812-8581, Japan e Toshiba Solutions Corporation, Toshiba Building 1-1, Shibaura 1-chome, Minato-ku, Tokyo 105-6691, Japan |
| Abstract: | In this paper, we study how to collect n balls moving with a fixed constant velocity in the Euclidean plane by k robots moving on straight track-lines through the origin. Since all the balls might not be caught by robots, differently from Moving-target TSP, we consider the following 3 problems in various situations: (i) deciding if k robots can collect all n balls; (ii) maximizing the number of the balls collected by k robots; (iii) minimizing the number of the robots to collect all n balls. The situations considered in this paper contain the cases in which track-lines are given (or not), and track-lines are identical (or not). For all problems and situations, we provide polynomial time algorithms or proofs of intractability, which clarify the tractability-intractability frontier in the ball collecting problems in the Euclidean plane. |
| Keywords: | Moving-target TSP Vehicle routing problem Partially ordered set Combinatorial optimization |
| 本文献已被 ScienceDirect 等数据库收录！ | |