Result: How to collect balls moving in the Euclidean plane
Title:
How to collect balls moving in the Euclidean plane
Authors:
Source:
Discrete algorithms and optimization, in honor of professor Toshihide Ibaraki at his retirement from Kyoto UniversityDiscrete applied mathematics. 154(16):2247-2262
Publisher Information:
Amsterdam; Lausanne; New York, NY: Elsevier, 2006.
Publication Year:
2006
Physical Description:
print, 19 ref
Original Material:
INIST-CNRS
Subject Terms:
Control theory, operational research, Automatique, recherche opérationnelle, Computer science, Informatique, Mathematics, Mathématiques, Sciences exactes et technologie, Exact sciences and technology, Sciences et techniques communes, Sciences and techniques of general use, Mathematiques, Mathematics, Combinatoire. Structures ordonnées, Combinatorics. Ordered structures, Ordre, treillis, structures algébriques ordonnées, Order, lattices, ordered algebraic structures, Sciences appliquees, Applied sciences, Recherche operationnelle. Gestion, Operational research. Management science, Recherche opérationnelle et modèles formalisés de gestion, Operational research and scientific management, Optimisation. Problèmes de recherche, Optimization. Search problems, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Automatique théorique. Systèmes, Control theory. Systems, Robotique, Robotics, Ensemble partiellement ordonné, Partially ordered set, Conjunto parcialmento ordenado, Informatique théorique, Computer theory, Informática teórica, Optimisation combinatoire, Combinatorial optimization, Optimización combinatoria, Robot mobile, Moving robot, Robot móvil, Algorithme QR, OR algorithm, Algorithme temps polynomial, Cible mobile TSP, Moving-target TSP, Intractabilité, Problème routage véhicule, Vehicle routing problem
Document Type:
Conference
Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Department of Social Information Systems, Faculty of Information Science, Kyushu Sangyo University. 2-3-1 Matsukadai, Higushi-ku, Fukuoka 813-8503, Japan
Department of Communications and Computer Engineering, Graduate School of Informatics, Kyoto University, Kyoto 606-8501, Japan
Department of Mathematical Informatics, Graduate School of Information and Technology, University of Tokyo, Tokyo 113-8656, Japan
Department of Computer Science and Communication Engineering, Graduate School of Information Science and Electrical Engineering Kyushu University, Fukuoka 812-8581, Japan
Toshiba Solutions Corporation, Toshiba Building 1-1, Shibaura 1-chome, Minato-ku, Tokyo 105-6691, Japan
Department of Communications and Computer Engineering, Graduate School of Informatics, Kyoto University, Kyoto 606-8501, Japan
Department of Mathematical Informatics, Graduate School of Information and Technology, University of Tokyo, Tokyo 113-8656, Japan
Department of Computer Science and Communication Engineering, Graduate School of Information Science and Electrical Engineering Kyushu University, Fukuoka 812-8581, Japan
Toshiba Solutions Corporation, Toshiba Building 1-1, Shibaura 1-chome, Minato-ku, Tokyo 105-6691, Japan
ISSN:
0166-218X
Rights:
Copyright 2006 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Mathematics
Operational research. Management
Mathematics
Operational research. Management
Accession Number:
edscal.18240643
Database:
PASCAL Archive
Further Information
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.