6
$\begingroup$

This is a cross-post from a question I asked on cs.stackexchange 2 weeks ago with no answers. I thought it might find home here.

We are given sorted $0\leq x_1 \leq x_2 \leq \dots \leq x_n$ and $y_1 \geq y_2 \geq \dots \geq y_n \geq 0$ non-negative integers accessible through oracles, with the additional constraints $x_{i+1}-x_i \leq 1$ and $y_i - y_{i+1} \leq 1$. Can we approximate the minimum of $x_i + y_i$ with $o(n)$ oracle queries to $x_i$, $y_i$ values, or is $\Omega(n)$ required?

For the exact case, a simple adversarial example can prove that you need to check all $n$ indices to find the minimum exactly (described in the link above).

A $2$-approximation can be taken by returning the index $i$ that minimizes $|x_i-y_i|$. This can be done using binary search using $O(\log n)$ queries.

Can we do better than a $2$-approximation in $o(n)$?

$\endgroup$
1
  • $\begingroup$ For completeness, worth adding a brief argument for the 2-approximation, maybe. $\endgroup$
    – Clement C.
    Commented Oct 3, 2022 at 6:42

1 Answer 1

5
$\begingroup$

Theorem 1. For any $\epsilon>0$, there is a $(1+\epsilon)$-approximation algorithm that makes $O(\epsilon^{-1}\log n)$ queries.

Note that if $\epsilon$ is arbitrarily small but constant, the algorithm makes $O(\log n)$ queries.

Before we prove the theorem, we prove the following utility lemma:

Lemma 1. Let $P_1, P_2, \ldots, P_m$ be a partition of the indices $[n]$, and for each $\ell\in [m]$ let $a(\ell)$ be a $(1+\epsilon)$-approximate solution to the subproblem induced by $P_\ell$. That is, $$x_{a(\ell)} + y_{a(\ell)} \le (1+\epsilon) \big(\min_{i\in P_\ell} x_i + y_i\big).$$ Let $a(\ell^*)$ be the best of these approximation solutions. That is, $\ell^* = \arg\min_\ell \{x_{a(\ell)} + y_{a(\ell)}\}$. Then $a(\ell^*)$ is a $(1+\epsilon)$-approximate solution to the original problem.

Proof. For any $i\in[n]$, we have, for $\ell$ such that $i\in P_\ell$, $$x_i + y_i \ge (x_{a(\ell)} + y_{a(\ell)})/(1+\epsilon) \ge (x_{a(\ell^*)} + y_{a(\ell^*)})/(1+\epsilon).~~~~~\Box$$

Now we prove the theorem. Here is the algorithm. First, using a single binary search on $x_i/y_i$, find $h = \max\{i\in [n] : x_i / y_i \le 1\}$. (Note that $x_i/y_i$ is increasing with $i$, so this takes $O(\log n)$ queries.)

Now partition the index set $[n]$ into two parts: $\{1, \ldots, h\}$ and $\{h+1, \ldots, n\}$. First compute a $(1+\epsilon)$-approximate solution to the subproblem induced by the first part $\{1, \ldots, h\}$ as follows.

Fix integer $k = \lceil 1/\epsilon\rceil$. Using $k-1$ binary searches, partition the index set $[h]$ into $k$ parts, where, for each $\ell\in [k]$, each index $i$ in the $\ell$th part $P_\ell$ satisfies $$(\ell-1)/k \le x_i / y_i \le \ell/k.$$ [For intuition, note that this condition is equivalent to $$y_i (1+(\ell-1)/k) \le x_i + y_i \le y_i(1 + \ell/k),$$ so that within the part we have $$x_i + y_i = (1+O(1/k))(1+(\ell-1)/k) y_i,$$ that is, the value $(1+(\ell-1)/k) y_i$ is a $(1+O(\epsilon))$-approximation to $x_i + y_i$.]

Now, for each $\ell\in [k]$, let $a(\ell)$ be the index $i$ in the $\ell$th part $P_\ell$ minimizing $y_i$. Note that $y_i$ is non-increasing with $i$, so we can just take $a(\ell) \gets \min P_\ell$, without doing additional queries.

Note that $a(\ell)$ is a $(1+\epsilon)$-approximate solution to the subproblem induced by $P_\ell$, because for any $i\in P_\ell$ we have $$x_i + y_i \ge y_i(1+(\ell-1)/k) \ge y_{a(\ell)}(1+(\ell-1)/k) \ge (x_{a(\ell)} + y_{a(\ell)})\alpha(k, \ell),$$ where $$\alpha(k, \ell) = \frac{1+(\ell-1)/k)}{1+\ell/k} = \frac{k+\ell-1}{k+\ell} = 1 - \frac{1}{k+\ell} \ge 1- \frac{1}{k+1} = \frac{1}{1+1/k} \ge \frac{1}{1+\epsilon}.$$

By Lemma 1, this gives us a $(1+\epsilon)$-approximate solution to the first part $[h]$ of $[n]$, using $O(\epsilon^{-1} \log n)$ queries. Similarly (exchanging the roles of $x$ and $y$) we can compute a $(1+\epsilon)$-approximate solution to the second part $[n]\setminus[h]$ using $O(\epsilon^{-1} \log n)$ queries. By Lemma 1, taking the best of these two solutions gives us a $(1+\epsilon)$-approximate solution to the original problem, in $O(\epsilon^{-1} \log n)$ queries.$~~~\Box$

$\endgroup$
1
  • $\begingroup$ Really nice idea. I'm assuming the intuition for it is using the $2-$approximation idea (of $x_i$ being close to $y_i$) to get a refinement where $x_i$ is "close enough" to $y_i$ in one of the subintervals? Thank you. $\endgroup$ Commented Oct 3, 2022 at 1:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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