3 ms·
Well, a lot of them can approximate "the" answer to within an arbitrarily and provably small amount, so it's definitions. For example, there is a polynomial-tim
by saulrh 15y ago
Well, a lot of them can approximate "the" answer to within an arbitrarily and provably small amount, so it's definitions. For example, there is a polynomial-time approximation for euclidean TSP that produces a solution with length at most (1 + epsilon) * optimal.
- ars 15y agoThat still doesn't answer: Is this formula convex or not. It's a yes or no question, not a probabilistic one. A probabilistic answer may be useful! But that's not the point of this proof.