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.



Linear program to maximize the minimum absolute value of linear functions ?
Unfortunately, this problem can't be represented by an LP, since your feasible region is in general nonconvex, and the feasible region of an LP (being the intersection of a bunch of half spaces) is always convex. 


To be more specific, consider the problem


$\max \;t $


$ t \leq | x- 1/2 | $


$ t \leq | x- 3/4 | $


$ 0 \leq x \leq 1 $


A sketch of the feasible region shows that it's nonconvex. There's a local maximum at $x=5/8$, $t=1/8$, and a global maximum at at $x=0$, $t=1/2$. 


