Binary Search with Distance-Dependent Costs

Calvin Leng, David KempearXiv 2023 · OpenReview

TL;DR

This paper introduces a generalized binary search problem where the cost of a query increases with its distance from the true target, reflecting real-world scenarios like pricing or dosage adjustments. They show that standard Binary Search is a constant-factor approximation for symmetric costs and that optimal solutions can be found efficiently for polynomial costs using dynamic programming, even extending this to tree structures.

What Problem Does This Paper Address?

The classic Binary Search algorithm is incredibly efficient for finding a target in a sorted list, assuming each query has a uniform cost. However, many real-world applications involve non-uniform costs. Imagine setting a price for an item: a price too high means no sale (opportunity cost), and a price too low means lost revenue. Similarly, adjusting a thermostat or medicine dosage incurs costs that grow the further you are from the ideal setting. This paper addresses this gap by introducing a model where the cost of a query is a non-decreasing function of the distance between the query and the true, adversarially chosen target. A key challenge is that the algorithm doesn't know the incurred cost until the very end when the target is revealed.

Methods

The authors tackle this problem in stages. For the simplest case on a line with symmetric costs (cost is the same whether you're too high or too low by the same amount), they prove that the standard Binary Search algorithm is a 4-approximation. When the cost functions are bounded-degree polynomials (even asymmetric ones), they develop a dynamic programming approach. This DP relies on a clever encoding of the "state" of past queries, summarizing their impact on future costs without needing to store every query individually. They then extend this to searching on trees. Here, instead of "too high" or "too low," a query tells you which branch of the tree contains the target. They leverage a framework called "k-cut search trees" to manage the complexity of tree structures and adapt their DP ideas to achieve a Polynomial Time Approximation Scheme (PTAS).

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Cost is King, Not Just Guesses: The core insight is that in many practical search problems, the quality of a guess (how close it is to the target) matters more than just the number of guesses. This shifts the focus from minimizing query count to minimizing cumulative cost.
  • Dynamic Programming with Clever State Encoding: The DP approach for polynomial costs is a significant technical contribution. The ability to summarize the impact of past queries into a compact set of coefficients (representing the cost function's polynomial form) is crucial for making the DP tractable.
  • Bridging the Gap from Lines to Trees: Extending the problem from a 1D line to a tree structure is non-trivial. The use of k-cut search trees and the careful analysis of how promotions affect costs are key to achieving a PTAS for trees.
  • Adversarial Model is Powerful: The assumption of an adversarial target choice, while challenging, allows for robust guarantees that hold against the worst possible scenarios.

Key Results

  • Binary Search is a 4-Approximation: For symmetric, monotone cost functions on a line, standard Binary Search achieves a cost within 4 times the optimal.
  • Optimal for Polynomial Costs: For cost functions that are bounded-degree polynomials, an optimal search strategy can be found in polynomial time on a line.
  • PTAS for Trees: For trees with bounded-degree polynomial distance-based costs, a Polynomial Time Approximation Scheme (PTAS) is provided, meaning they can find a solution arbitrarily close to optimal.

Limitations and Future Work

The authors acknowledge that their 4-approximation for Binary Search might not be tight and that a tighter bound is an interesting direction. They also note that their DP approach for polynomial costs on a line doesn't directly extend to more general cost functions beyond polynomials. For trees, they don't know if the problem is NP-hard to solve optimally. Future work includes exploring more general cost functions, investigating approximation guarantees for arbitrary (or convex) cost functions on trees, and extending the model to general graphs. They also suggest exploring scenarios with noisy answers or assuming a known distribution for the target instead of an adversarial one.

Summary updated

Abstract

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.
BibTeX
@misc{leng2023binary,
  author = {Calvin Leng and David Kempe},
  title = {{Binary Search with Distance-Dependent Costs}},
  year = {2023},
  eprint = {2303.06488},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2303.06488},
}

Loading related content...

Figure