Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency
Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency
复制标题
具有最小-最大延迟的多机器人巡逻调度近似算法
DOI：
10.1007/978-3-030-66723-8_7
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Yang, Hao-Tsung
中科院分区：
文献类型：
--
作者：
Afshani, Peyman;de Berg, Mark;Buchin, Kevin;Gao, Jie;Löffler, Maarten;Nayyeri, Amir;Raichel, Benjamn;Sarkar, Rik;Wang, Haotian;Yang, Hao-Tsung
我们考虑在度量空间中寻找机器人访问给定n个站点的巡逻时间表的问题。每个机器人具有相同的最大速度，目标是最小化任何站点的加权最大延迟，其中站点的延迟定义为该站点连续访问之间的最大持续时间。这个问题是NP难的，因为它有旅行推销员问题作为一个特殊情况（当所有网站都有相同的权重）。我们提出了一个多项式时间算法，逼近因子为，其中和分别是站点的最大和最小权重。此外，我们考虑的特殊情况下，网站是在1D。当所有站点具有相同的权重时，我们提出了一个多项式时间算法来精确求解该问题。如果站点可能具有不同的权重，我们会提出一个12近似的解决方案，该解决方案在时间上运行。
We consider the problem of finding patrol schedules forkrobots to visit a given set ofnsites in a metric space. Each robot has the same maximum speed and the goal is to minimize the weighted maximum latency of any site, where the latency of a site is defined as the maximum time duration between consecutive visits of that site. The problem is NP-hard, as it has the traveling salesman problem as a special case (whenand all sites have the same weight). We present a polynomial-time algorithm with an approximation factor ofto the optimal solution, whereandare the maximum and minimum weight of the sites respectively. Further, we consider the special case where the sites are in 1D. When all sites have the same weight, we present a polynomial-time algorithm to solve the problem exactly. If the sites may have different weights, we present a 12-approximate solution, which runs in time.
登录
查看更多内容
影响因子：
2.5
作者：
Arora, S
通讯作者：
Arora, S
任意固定维数欧氏空间中最小权k尺寸循环覆盖问题的多项式时间逼近方案
影响因子：
--
作者：
M. Khachay;Katherine Neznakhina
通讯作者：
Katherine Neznakhina
范围聚类查询
DOI：
10.4230/lipics.socg.2017.5
发表时间：
2017
期刊：
The Journal of biological chemistry
影响因子：
--
作者：
Mikkel Abrahamsen;M. D. Berg;K. Buchin;M. Mehr;Ali D. Mehrabi
通讯作者：
Ali D. Mehrabi
DOI：
10.1016/j.jcss.2019.02.002
发表时间：
2019
期刊：
J. Comput. Syst. Sci.
影响因子：
--
作者：
Nir Drucker;M. Penn;O. Strichman
通讯作者：
O. Strichman