1
$\begingroup$

Given an algorithm with approximation ratio $\alpha$, and another algorithm with approximation ratio $\beta=n^\epsilon$, and a solution to a problem with cost $c$. What is the standard way to bound $\alpha$ in terms of $\beta$ if $(n-c) \leq \alpha (n- \beta c)$. That is, what can I say about $\alpha$ in terms of $\beta$ (assuming all positives, and $c < n$).

$\endgroup$

closed as off-topic by Yuval Filmus, R B, Tsuyoshi Ito, Kristoffer Arnsfelt Hansen, Radu GRIGore Nov 5 '14 at 8:19

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Yuval Filmus, Kristoffer Arnsfelt Hansen, Radu GRIGore
If this question can be reworded to fit the rules in the help center, please edit the question.