In this paper by Arora, Hazan, and Kale ([http://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf][1]) a method is given for using the Multiplicative Weights Update algorithm to quickly solve Linear Programs based on the framework by Plotkin, Shmoys, and Tardos.

One section assumes the existence of an 'ORACLE' that can quickly solve the following problem:
$$\alpha x \geq \beta$$
for
$$ x \in \mathbb{R}^n $$
such that
$$ x \geq 0,\; c \cdot x = OPT$$
for some 
$$\beta \in \mathbb{R}, \; OPT \in \mathbb{R}, \; c \in \mathbb{R}^n$$

I imagine this should be fairly simple, the algorithm needs to just find any feasible $x$ in the convex set of $K = \;${$x \in \mathbb{R}^n \; | \;  x \geq 0,\; c \cdot x = OPT $} or output 'INFEASIBLE' if no such $x$ exists.  Ideally this would be done in $O(n)$ time but I'm not sure if that's possible.

Does anyone know of such an algorithm?  The authors of the paper seem to suggest that such a problem is trivial so I'd imagine there is literature somewhere that solves my problem.


  [1]: http://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf