论文标题
提示在线搜索
Online Search With a Hint
论文作者
论文摘要
线性搜索问题（非正式地称为牛路问题）是搜索理论中的基本问题之一。在此问题中，固定目标隐藏在无限线上的某个未知位置上，最初位于称为根的某个特定点的移动搜索器必须穿越该行以定位目标。目的是最大程度地减少搜索者与目标距离距离距离的距离的最差比率，这被称为搜索的竞争比。 在这项工作中，我们在搜索者有关于目标的暗示的环境中研究了这个问题。关于提示的性质，我们考虑三个设置：i）提示表明目标在线上的确切位置； ii）提示提出了最佳搜索的方向（即，在根的左侧或右侧）； iii）提示是一个通用的k位字符串，它编码有关目标的一些信息。我们的目标是研究该模型中策略的帕累托效率。也就是说，如果提示正确（即由受信任的来源提供），并且提示不正确（即，即由对手提供），则我们在搜索者的性能之间寻求最佳或几乎最佳的权衡。
The linear search problem, informally known as the cow path problem, is one of the fundamental problems in search theory. In this problem, an immobile target is hidden at some unknown position on an unbounded line, and a mobile searcher, initially positioned at some specific point of the line called the root, must traverse the line so as to locate the target. The objective is to minimize the worst-case ratio of the distance traversed by the searcher to the distance of the target from the root, which is known as the competitive ratio of the search. In this work we study this problem in a setting in which the searcher has a hint concerning the target. We consider three settings in regards to the nature of the hint: i) the hint suggests the exact position of the target on the line; ii) the hint suggests the direction of the optimal search (i.e., to the left or the right of the root); and iii) the hint is a general k-bit string that encodes some information concerning the target. Our objective is to study the Pareto-efficiency of strategies in this model. Namely, we seek optimal, or near-optimal tradeoffs between the searcher's performance if the hint is correct (i.e., provided by a trusted source) and if the hint is incorrect (i.e., provided by an adversary).
