We introduce a search problem generalizing the typical setting of Binary Search on the line. Similar to the setting for Binary Search, a target is chosen adversarially on the line, and in response to a query, the algorithm learns whether the query was correct, too high, or too low. Different from the Binary Search setting, the cost of a query is a monotone non-decreasing function of the distance between the query and the correct answer; different functions can be used for queries that are too high vs. those that are too low. The algorithm's goal is to identify an adversarially chosen target with minimum total cost. Note that the algorithm does not even know the cost it incurred until the end, when the target is revealed. This abstraction captures many natural settings in which a principal experiments by setting a quantity (such as an item price, bandwidth, tax rate, medicine dosage, etc.) where the cost or regret increases the further the chosen setting is from the optimal one. First, we show that for arbitrary symmetric cost functions (i.e., overshooting vs. undershooting by the same amount leads to the same cost), the standard Binary Search algorithm is a 4-approximation. We then show that when the cost functions are bounded-degree polynomials of the distance, the problem can be solved optimally using Dynamic Programming; this relies on a careful encoding of the combined cost of past queries (which, recall, will only be revealed in the future). We then generalize the setting to finding a node on a tree; here, the response to a query is the direction on the tree in which the target is located, and the cost is increasing in the distance on the tree from the query to the target. Using the k-cut search tree framework of Berendsohn and Kozma and the ideas we developed for the case of the line, we give a PTAS when the cost function is a bounded-degree polynomial.
翻译:我们引入了对线上的 Binary 搜索的典型设置进行一般化的搜索问题。 与 Binary 搜索的设置相似, 目标在线上以对称方式选择目标, 并且作为对询问的响应, 算法会了解查询是否正确、 过高或过低。 不同于 Binary 搜索的设置, 查询的成本是查询和正确答案之间距离的单调非递减功能; 不同的功能可用于查询太高或太低的。 算法的目标是在线上辨别一个对抗性选择的目标, 且总成本为最小。 注意, 算法甚至不知道它直到目标被显示后才发生的成本。 这种抽象化可以捕捉到许多自然设置, 通过设定数量( 如项目价格、 带宽、 税率、 医药剂量等), 当选择的设置比重更远的设置比重, 我们只能提供最优的。 首先, 我们显示任意的排序成本函数( i. g. g. g. g. g. g. g.</s>