6
$\begingroup$

Let $f:\{1,\ldots,n\}$ be a monotonically non-decreasing function.

Consider, for some unknown threshold $1\le T\le n$, a threshold function $$g(x)= \begin{cases} 0&\text{x<T}\\ 1&\text{otherwise}. \end{cases}$$

Our goal is to find $T$ while minimizing the worst case cost, where computing $g(x)$ for any $x\in\{1,\ldots n\}$ has a cost of $f(x)$. We assume that $f$ is known.

There are two straightforward approaches for this: a linear scan and a binary search.

It's not hard to see that each of them is good for different scenarios -- a linear scan works fine for $f(x)=2^{x}$ while a binary search is optimal for $f(x)=1$.

Since $f(n/2)$ may be much larger than $f(T)$, another approach is to use doubling and then binary search. The cost of this is bounded by $O(f(2T)\log T)$. This can be modified to $$O(\epsilon^{-1} f(T)\log T + f(T(1+\epsilon))\log (T\epsilon))$$ by doing the doubling using a $(1+\epsilon)$ factor.

If this problem is known, What is the name of this problem?

What is the optimal strategy here?


Obviously, it is possible to exhaustively compute the correct strategy. Can we compute it (or an approximation of it) faster? Is it possible to give an analytical formula for it?

I am aware that the problem is somewhat vague. Mainly, I am wondering if it is possible to analytically find an optimal solution (using the $f(i)$ values) and if not, if it is possible to compute a reasonable strategy given $f$ as an input. You may also assume additional reasonable properties on $f$.

$\endgroup$
3
$\begingroup$

The optimal strategy can be found through dynamic programming in $O(n^3)$ time. Let $A[i,j]$ denote the worst-case cost of the optimal strategy when $T$ is already known to be in $\{i,i+1,\dots,j\}$. Then we have the recursive relation

$$A[i,k] = \min \{f(j) + \max(A[i,j], A[j+1,k]) : j=i,i+1,\dots,k-1\},$$

with the base case $A[i,i] = 0$. You can use dynamic programming to fill out this array. The assumption that $f$ is non-decreasing is not needed; this works whenever $f$ is any non-negative function.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.