An oracle typically is treated as a black box subroutine. Measuring algorithms in how

many oracle calls are used in the worst case is often a powerful theoretical framework for

optimization problems. For the purposes of this exercise, a feasibility oracle $($A$,$ b$)$ takes

as input A in R

m$\backslash$times n

$,$ b in R

m for some integers m and n$,$ and outputs

i$.$ If Ax $<=$ b is infeasible, outputs the pair $($A$,$ b$)$ is infeasible;

ii$.$ Otherwise, outputs a point $$x such that A$$x $<=$ b$.$

Consider the following linear program

maximize: c

T x

subject to: Bx $<=$ d$.$

Furthermore, suppose the linear program is bounded and feasible, and let P be the set of

feasible points and let OP T be the optimal value. Suppose you know $0<=$ OP T $<=$ M$.$ For

all $\backslash$epsi $>0,$ show with at most $$log$2$

$($M$/\backslash$epsi $)+1$ calls to $,$ one can find a feasible solution

z in P such that $|$c

T z $$ OP T$|<=\backslash$epsi