$l^\infty$-minimization with one parameter - explicit solution formula available? Given two vectors $a,b\in \mathbb R^n$, I want to solve the (one-dimensional) minimization problem
$$
\min_{s\in \mathbb R} \|a - bs\|_\infty.
$$
We can assume that $b\ge0$. In the case that all entries of $b$ are equal to one, then a solution of the above problem is given by
$$
s = \frac12( \min_ia_i + \max_ia_i).
$$
Is there a similar (easy) solution formula available if $b$ has at least two different entries?
Or is there a method to  compute the solution in $O(n)$ operations?
I know that the above problem can be formulated as standard linear programming problem and solved as such.
 A: Here is a solution in $O(n \log n)$.
By doubling (and modifying) the entries in $a,b$, we can reformulate the problem as
$$\min_{s \in \mathbb R} \max( a + s b ),$$
where $\max$ denotes the maximal entry of a vector.
This problem can be cast as the following linear problem
\begin{align*}
\text{Minimize} \quad & t \\
\text{s.t.} \quad & a + s b \le t e.
\end{align*}
Here, $e$ is the all-one-vector. Its dual problem is (equivalent to)
\begin{align*}
\text{Maximize} \quad&a^\top \lambda \\
\text{such that} \quad & b^\top \lambda = 0 \\
& e^\top \lambda = 1\\
& \lambda \ge 0.
\end{align*}
This problem has a nice geometrical interpretation: We look for a point in the convex hull of $\{(a_i,b_i) | i = 1,\ldots,n\}$ whose $y$-coordinate is zero and whose $x$-coordinate is as big as possible.
It is possible to compute the convex hull (and thus, to solve the dual problem) in $O(n \log n)$. From the dual solution, one can reconstruct the primal solution.
Since we do not need the full convex hull, it is maybe possible to solve the dual problem faster than $O(n \log n)$, but I do not have any idea how to accomplish that.
