Given sorted $0\leq x_1 \leq x_2 \leq ... \leq x_n$ and $y_1 \geq y_2 \geq ... \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, the following example shows we need to read all indices to determine the minimum: $x_i=i$ and $y_i=n+1-i$. If the algorithm doesn't read one index (say index $k$), then the adversary can set $x_k=k, y_k=n+1-k$ so that the overall minimum is $n+1$, or is can set $x_k=k-1=x_{k-1}$ and $y_k=n+1-i$, at which case the overall minimum is $n$. So the algorithm needs to read all $n$ bits to differentiate inputs.

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

Can we do better (either approximation constant or number of queries)?

  • $\begingroup$ Cross-posted here: cstheory.stackexchange.com/questions/51954/… $\endgroup$ Oct 2, 2022 at 3:20
  • $\begingroup$ cs.stackexchange.com/questions/69872/… $\endgroup$
    – D.W.
    Oct 2, 2022 at 23:09
  • $\begingroup$ I’m voting to close this question because it was cross-posted. $\endgroup$
    – D.W.
    Oct 2, 2022 at 23:09
  • $\begingroup$ @D.W. I feel this policy needs revisiting. If a question hasn't been answered for 13 days, it's most likely not going to be answered in one over the other and waste people's time (as the comment you link to insinuates). Specially with the author linking to the cross-post and explicitly making both communities aware of the cross-post... $\endgroup$ Oct 3, 2022 at 1:30
  • $\begingroup$ @AspiringMat What you did was correct, and I don’t think the comment on wasting time is appropriate. However, it may still make sense to close the question here, so that only one instance is active at a time. Also, please, include the link to the cross-post in the body of the question, not just in comments, which are of transient nature. $\endgroup$ Oct 3, 2022 at 7:50


Browse other questions tagged or ask your own question.