New answers tagged approximation-algorithms
0
The compendium from Crescenzi is the most complete that I am aware of, despite being pretty old now. You can also watch this more recent (still twelve years old) survey:
Vangelis Paschos. An overview on polynomial approximation of NP-hard problems.
https://hal.archives-ouvertes.fr/hal-00186549/document
1
Since it is asymptotic approximation and epsilon is a constant, for OPT big enough being 1 off is always good.
Let's put it another way. Either your optimal is smaller than 1/epsilon and you can find it within polynomial time. Or it is not and thus 1+1/OPT is better than 1+epsilon.
4
The following website seems to be no longer maintained, but it is still a useful resource because it covers many problems: http://www.csc.kth.se/~viggo/problemlist/
4
Not a complete answer, but hopefully a good starting point. It is very instructive to (always!) first consider the discrete analog of your question. If $X$ is some set and $f:X\to\{0,1\}$, what is the minimal number of evaluation queries needed to uniquely identify $f$? As already noted in the OP, the question only makes sense if one fixes a function class $...
Top 50 recent answers are included
