Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

In this paper by Arora, Hazan, and Kale (http://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf) 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.

share|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.