I'd like to compute

$\max_{x,t} t$ such that $\forall i$, $t < a_i + |x - b_i|$.

where $a_i,\ldots, a_n$ and $b_1,\ldots,b_n$ are fixed and $x \in [0,1]$.

Can this be solved with a linear program? I'm familiar with a technique to minimize the maximum of absolute values, by doubling the number of constraints, but I don't think it applies to maximizing the minimum.

If a linear program won't work, is there another efficient way to get an exact solution?

Thanks much.

3more comments