Suppose $$ a_i = x_i+ b_i , \qquad i=1,\ldots,n, $$ where $a_1,\ldots,a_n \in \mathbb{R}$ are known, $x_i\geq 0$ is unknown and $b_1,\ldots,b_n \in \mathbb{R}$ are known to take one of the values $ b_{(1)}<\ldots<b_{(n)}$ but which value exactly is unknown.
I am interested in lower bounds for $\min\{x_i\}$.
My questions:
(1) What are some lower bounds for $\min\{x_i\}$ in terms of $a_1,\ldots,a_n$ and $b_{(1)}<\ldots<b_{(n)}$?
(2) What is the best lower bound for $\min\{x_i\}$ in terms of $a_1,\ldots,a_n$ and $b_{(1)}<\ldots<b_{(n)}$?
(3) Are there some papers on this or similar problems?
(4) Same questions as (1)-(3) except for upper bounds (but I am more interested in lower bounds).
My answers:
(1)-(2) The best (and only) lower bound I was able to obtain is:
$$ x_{(1)}=\min\{x_i\}=\min\{a_i-b_i\}\geq \min\{a_i\}-\max\{b_i\}=a_{(1)}-b_{(n)}, $$ where $a_{(1)}=\min\{a_i\}$.
A proof that I thought would be useful to extend is based on the pigeonhole principle. Specifically, suppose that the above does not hold so that $x_{(1)}< a_{(1)}-b_{(n)}$ then $$ a_{(1)} > x_{(1)} + b_{(n)}\geq x_{(1)} +b_j, \qquad j=1,\ldots,n, $$ but $a_k= x_{(1)} +b_j$ for some $k$ and so $a_k<a_{(1)}$. A contradiction.
(3) I have been searching through the literature on "sumsets" but haven't found anything related (note: $x_i$ does not need to be discrete). I also looked into deconvolutions but wasn't able to find anything. Also, the "Similar questions" were on optimization but I wasn't able to make a useful connection after reformulating the problem into $\min\{x_i\}$ s.t. $x_i=a_i-b_i$.
If you order the $a_i$ in ascending (or at least non-descending) order as
$$a_{(1)} \le a_{(2)} \le \ldots \le a_{(n)}$$
then a necessary and sufficient condition for a solution $x_i \ge 0$ to exist is that
$$\forall 1 \le i \le n: a_{(i)} \ge b_{(i)}.$$
It's clear that it is sufficient. It's also necessary, because if $k$ is the smallest index with $a_{(k)} < b_{(k)}$, then in a solution at least one of $a_{(1)}, a_{(2)},\ldots a_{(k)}$ would be matched with a $b_{(l)}$ with $l \ge k$ (there are only $k-1$ smaller possible $l$'s). Since $a_{(k)}$ is the biggest of these $a$'s and $b_{(k)}$ the smallest of these $b$'s, their difference would be negative, in contrast to the condition that all $x_i$ must be non-negative.
Now, the actual minimum $x_i$ possible is
$$\min_{1\le i \le n, i \le j \le n} \{a_{(i)}-b_{(j)}: a_{(i)}-b_{(j)} \ge 0\}.$$
Since the $a_{(i)},b_{(j)}$ are already ordered, that takes $O(\log_2(n-i+1))$ steps for a given $i$ to find (use binary search where exactly the difference goes from non-negative to negative). Summed over all $i$ this yields a complexity of $O(\log_2(n!))=O(n\log_2(n))$, so nothing more that already sorting the $a_{(i)},b_{(j)}$.