Approximation Algorithms for a Location-Based Group Gathering Service with Multiple Roles

摘要

We study the problem of a location-based group gathering service (LGS) with the objective of minimizing the time for agents such as people or robots to meet in a two-dimensional space. A need for LGS occurs in many situations such as soldier rescue in battle fields, family gathering at a parking lot, airport shuttle(s) pick-up and drop off of people, and robot cooperation. We consider two agent roles: receivers and providers. Receivers (e.g. elderly, disabled, wounded) cannot move to the final location until they are "picked up" by providers. We name this problem location-based group gathering service with provider-receiver constraint (LGS-PRC). We formulate LGS-PRC and prove it is NP-complete. Accordingly, we provide an approximation algorithm, Partition-Assignment Gathering (PAG), and prove it achieves a constant approximation ratio compared to the lower bound. Numerical results show PAG is within the approximation ratio, and that it outperforms the algorithm that assigns the closest provider to a receiver.