论文标题
频率竞争性的查询策略，以保持移动实体之间的拥塞潜力较低
Frequency-Competitive Query Strategies to Maintain Low Congestion Potential Among Moving Entities
论文作者
论文摘要
我们考虑使用位置查询来监测一个实体搬运的拥堵潜力的问题，速度有界，但在$ d $ d $维的欧几里得空间中进行了不可预测的问题。由于查询之间的潜在运动而导致的实体位置的不确定性会导致每个时间时刻可能的实体配置的空间，并且可能具有截然不同的拥堵属性。我们根据与实体相关的不确定性区域的（动态）相交图来定义我们所谓的交通拥堵潜力的不同度量，以描述可能发生的拥塞。 在相同的不确定性模型中，先前的工作[Socg'13，Eurocg'14，Sicomp'16，Soda'19]解决了使用某些有界频率的位置查询来最大程度地减少充血电位的问题。结果表明，就最差的拥塞潜力而言，有可能设计一个$ o（1）$的查询方案，而其他千里眼的查询方案（知道所有实体的轨迹），但要受查询频率相同的限制。 在本文中，我们解决了双重问题：如何保证以任何固定时间间隔在查询总数（以查询总数或查询之间的最小间距（粒度）之间的最小程度来衡量的查询频率）上，在任何固定时间间隔内测量。这个互补目标需要完全不同的算法和分析。然而，我们的结果与早期论文的结果平行，特别是在所需的查询频率上具有紧密的竞争界限，并且存在一些令人惊讶的差异。
We consider the problem of using location queries to monitor the congestion potential among a collection of entities moving, with bounded speed but otherwise unpredictably, in $d$-dimensional Euclidean space. Uncertainty in entity locations due to potential motion between queries gives rise to a space of possible entity configurations at each moment in time, with possibly very different congestion properties. We define different measures of what we call the congestion potential of such spaces, in terms of the (dynamic) intersection graph of the uncertainty regions associated with entities, to describe the congestion that might actually occur. Previous work [SoCG'13, EuroCG'14, SICOMP'16, SODA'19], in the same uncertainty model, addressed the problem of minimizing congestion potential using location queries of some bounded frequency. It was shown that it is possible to design a query scheme that is $O(1)$-competitive, in terms of worst-case congestion potential, with other, even clairvoyant query schemes (that know the trajectories of all entities), subject to the same bound on query frequency. In this paper we address the dual problem: how to guarantee a fixed bound on congestion potential while minimizing the query frequency, measured in terms of total number of queries or the minimum spacing between queries (granularity), over any fixed time interval. This complementary objective necessitates quite different algorithms and analyses. Nevertheless, our results parallel those of the earlier papers, specifically tight competitive bounds on required query frequency, with a few surprising differences.
