2
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .