2
$\begingroup$

In the Conclusion section, the author of this paper "Stability of Approximation Algorithms for Hard Optimization Problems" by Juraj Hromkovič, 1999 claims that

Using the notion of stability one can search for a spectrum of the hardness of a problem according to the set of inputs. For instance, considering a hard problem like TSP one could get an infinite sequence of input languages $L_0, L_1, L_2, \ldots$ given by some distance measure, where $\epsilon_r(n)$ is the best achievable relative error for the language $L_r$.

As I understand, the notion of stability of approximation is relative to a specific problem $Q$ (e.g., TSP above), a specific approximation algorithm for some subproblem of $Q_0$ (corresponding to $L_0$ above), and a specific distance measure. Given that, how can we construct a spectrum of the hardness of of problem $Q$ according to their polynomial-time approximability? Specifically, how to show that "$\epsilon_r(n)$ is the best achievable relative error for the language $L_r$" using the concept of stability of approximation?

Concrete examples are appreciated.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.