$(10\%)$ The simplified two$-$variable linear programming problem is defined as follows:

Minimize $y$

Subject $toy{a}_{i}x+b_i(i=1,2,$dots,$n)$

As introduced in class, this problem can be solved by using the prune and search approach.

Please answer the following questions:

$($a$)(2\%)$ Let $(x_0,y_0)$ be an optimum solution and $F(x)=ma{x}_{1}in\{a_{i}x+b_i\}.$ Is it true that $x_0$

must satisfy $F(x_0)=mi{n}_{-}xF(x).$

$($b$)(2\%)$ Given a value $x_m,$ how do we know whether $x_0{x}_m$ or $x_0=x_m?$

$($c$)(2\%)$ If $x_m{|}_{{?}_{?}}\frac{n}{(4{)}_{{?}_{?}}}|x_0,$ then how can $we$ prune those constraints that are useless?

$(d)(2\%)$ How $dowe$ choose $x_{m}so$ that $we$ can prune ${|}_{{?}_{?}}\frac{n}{(4{)}_{{?}_{?}}}|$ constraints away for each iteration?

$(e)(2\%)$ What $is$ the time complexity $of$ this prune and search approach?