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

1 Answer 1

Actually, I guess that they do not mean that such an oracle always exists. Usually, the argument is of the form: If, for your special problem, you have a quick method of checking if this problem has a feasible solution, then you can apply it to solve the whole problem.

Generally, you can construct a vertex for your problem $K$ by choosing an index where $c_i$ has the same sign as OPT and then apply the simplex algorithm, maximizing $\alpha x$ until you pass $\beta$ or reach the optimum.

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.