# Approximation algorithm for minimising $x_i+y_i$ for monotonically increasing sequence $x_i$ and monotonically decreasing sequence $y_i$

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)$$?

• For completeness, worth adding a brief argument for the 2-approximation, maybe. Commented Oct 3, 2022 at 6:42

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$$

• 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. Commented Oct 3, 2022 at 1:28