<p><strong>Theorem 1.</strong> <em>For any <span class="math-container">$\epsilon&gt;0$</span>, there is a <span class="math-container">$(1+\epsilon)$</span>-approximation algorithm that makes <span class="math-container">$O(\epsilon^{-1}\log n)$</span> queries.</em></p>
<p>Note that if <span class="math-container">$\epsilon$</span> is arbitrarily small but constant,
the algorithm makes <span class="math-container">$O(\log n)$</span> queries.</p>
<p>Before we prove the theorem, we prove the following utility lemma:</p>
<p><strong>Lemma 1.</strong> <em>Let <span class="math-container">$P_1, P_2, \ldots, P_m$</span> be a partition of the indices <span class="math-container">$[n]$</span>, and for each <span class="math-container">$\ell\in [m]$</span> let <span class="math-container">$a(\ell)$</span> be a <span class="math-container">$(1+\epsilon)$</span>-approximate solution to the subproblem induced by <span class="math-container">$P_\ell$</span>.  That is,</em>
<span class="math-container">$$x_{a(\ell)} + y_{a(\ell)} \le (1+\epsilon) \big(\min_{i\in P_\ell} x_i + y_i\big).$$</span>
<em>Let <span class="math-container">$a(\ell^*)$</span> be the best of these approximation solutions.  That is,
<span class="math-container">$\ell^* = \arg\min_\ell \{x_{a(\ell)} + y_{a(\ell)}\}$</span>.  Then <span class="math-container">$a(\ell^*)$</span> is a <span class="math-container">$(1+\epsilon)$</span>-approximate solution to the original problem.</em></p>
<p><em>Proof.</em>  For any <span class="math-container">$i\in[n]$</span>, we have, for <span class="math-container">$\ell$</span> such that <span class="math-container">$i\in P_\ell$</span>,
<span class="math-container">$$x_i + y_i
 \ge (x_{a(\ell)} + y_{a(\ell)})/(1+\epsilon)
 \ge (x_{a(\ell^*)} + y_{a(\ell^*)})/(1+\epsilon).~~~~~\Box$$</span></p>
<p>Now we prove the theorem.  Here is the algorithm.  First, using a single binary search on <span class="math-container">$x_i/y_i$</span>, find <span class="math-container">$h = \max\{i\in [n] : x_i / y_i \le 1\}$</span>.  (Note that <span class="math-container">$x_i/y_i$</span> is increasing with <span class="math-container">$i$</span>, so this takes <span class="math-container">$O(\log n)$</span> queries.)</p>
<p>Now partition the index set <span class="math-container">$[n]$</span> into two parts: <span class="math-container">$\{1, \ldots, h\}$</span> and <span class="math-container">$\{h+1, \ldots, n\}$</span>.  First compute a <span class="math-container">$(1+\epsilon)$</span>-approximate solution to the subproblem induced by the first part <span class="math-container">$\{1, \ldots, h\}$</span> as follows.</p>
<p>Fix integer <span class="math-container">$k = \lceil 1/\epsilon\rceil$</span>.
Using <span class="math-container">$k-1$</span> binary searches, partition the index set <span class="math-container">$[h]$</span> into <span class="math-container">$k$</span> parts, where, for each <span class="math-container">$\ell\in [k]$</span>, each index <span class="math-container">$i$</span> in the <span class="math-container">$\ell$</span>th part <span class="math-container">$P_\ell$</span> satisfies
<span class="math-container">$$(\ell-1)/k \le x_i / y_i \le \ell/k.$$</span>
[For intuition, note that this condition is equivalent to
<span class="math-container">$$y_i (1+(\ell-1)/k) \le x_i + y_i \le y_i(1 + \ell/k),$$</span>
so that within the part we have
<span class="math-container">$$x_i + y_i = (1+O(1/k))(1+(\ell-1)/k) y_i,$$</span>
that is, the value <span class="math-container">$(1+(\ell-1)/k) y_i$</span> is a <span class="math-container">$(1+O(\epsilon))$</span>-approximation to <span class="math-container">$x_i + y_i$</span>.]</p>
<p>Now, for each <span class="math-container">$\ell\in [k]$</span>, let <span class="math-container">$a(\ell)$</span> be the index <span class="math-container">$i$</span> in the <span class="math-container">$\ell$</span>th part <span class="math-container">$P_\ell$</span> minimizing <span class="math-container">$y_i$</span>.  Note that <span class="math-container">$y_i$</span> is non-increasing with <span class="math-container">$i$</span>, so we can just take <span class="math-container">$a(\ell) \gets \min P_\ell$</span>, without doing additional queries.</p>
<p>Note that <span class="math-container">$a(\ell)$</span> is a <span class="math-container">$(1+\epsilon)$</span>-approximate solution to the subproblem induced by <span class="math-container">$P_\ell$</span>, because for any <span class="math-container">$i\in P_\ell$</span> we have
<span class="math-container">$$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),$$</span>
where
<span class="math-container">$$\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}.$$</span></p>
<p>By Lemma 1, this gives us a <span class="math-container">$(1+\epsilon)$</span>-approximate solution to the first part <span class="math-container">$[h]$</span> of <span class="math-container">$[n]$</span>, using <span class="math-container">$O(\epsilon^{-1} \log n)$</span> queries.  Similarly (exchanging the roles of <span class="math-container">$x$</span> and <span class="math-container">$y$</span>) we can compute a <span class="math-container">$(1+\epsilon)$</span>-approximate solution to the second part <span class="math-container">$[n]\setminus[h]$</span> using <span class="math-container">$O(\epsilon^{-1} \log n)$</span> queries.  By Lemma 1, taking the best of these two solutions gives us a <span class="math-container">$(1+\epsilon)$</span>-approximate solution to the original problem, in <span class="math-container">$O(\epsilon^{-1} \log n)$</span> queries.<span class="math-container">$~~~\Box$</span></p>

CC BY-SA 4.0
2022-10-03T01:28:51.420Z
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.
user3508551
CC BY-SA 4.0
2022-10-02T21:29:36.370Z
2022-10-02T21:29:36.370Z
Neal Young
<p>This is a cross-post from a <a href="https://cs.stackexchange.com/questions/154215/approximation-algorithm-for-minimising-x-iy-i-for-monotonically-increasing-se">question I asked on cs.stackexchange 2 weeks ago</a> with no answers. I thought it might find home here.</p>
<p>We are given sorted <span class="math-container">$0\leq x_1 \leq x_2 \leq \dots \leq x_n$</span> and <span class="math-container">$y_1 \geq y_2 \geq \dots \geq y_n \geq 0$</span> non-negative <strong>integers</strong> accessible through oracles, with the additional constraints <span class="math-container">$x_{i+1}-x_i \leq 1$</span> and <span class="math-container">$y_i - y_{i+1} \leq 1$</span>. Can we approximate the minimum of <span class="math-container">$x_i + y_i$</span> with <span class="math-container">$o(n)$</span> oracle queries to <span class="math-container">$x_i$</span>, <span class="math-container">$y_i$</span> values, or is <span class="math-container">$\Omega(n)$</span> required?</p>
<p>For the exact case, a simple adversarial example can prove that you need to check all <span class="math-container">$n$</span> indices to find the minimum exactly (described in the link above).</p>
<p>A <span class="math-container">$2$</span>-approximation can be taken by returning the index <span class="math-container">$i$</span> that minimizes <span class="math-container">$|x_i-y_i|$</span>. This can be done using binary search using <span class="math-container">$O(\log n)$</span> queries.</p>
<p><strong>Can we do better than a <span class="math-container">$2$</span>-approximation in <span class="math-container">$o(n)$</span>?</strong></p>

CC BY-SA 4.0
2022-10-03T06:42:02.393Z
For completeness, worth adding a brief argument for the 2-approximation, maybe.
Clement C.
<approximation-algorithms><oracles>
Approximation algorithm for minimising $x_i+y_i$ for monotonically increasing sequence $x_i$ and monotonically decreasing sequence $y_i$
user3508551
# Approximation algorithm for minimising $x_i+y_i$ for monotonically increasing sequence $x_i$ and monotonically decreasing sequence $y_i$

(Asked by: username_0 on 2022-10-02)

This is a cross-post from a [question I asked on cs.stackexchange 2 weeks ago](https://cs.stackexchange.com/questions/154215/approximation-algorithm-for-minimising-x-iy-i-for-monotonically-increasing-se) 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)$?**

**Tags:** approximation-algorithms, oracles
> **Comments:**
> **username_1**: For completeness, worth adding a brief argument for the 2-approximation, maybe.  

---

## 1 answers

### Answer by username_2 on 2022-10-02. Score: 5 | Accepted answer

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

> **Comments:**
> **username_0**: 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.  

---

