3 ms·
Worth noting here is that the approximation factor here is 5500. (I.e., the algorithm is only guaranteed to return a route whose length is no more than 5500 ti
by Sniffnoy 9y ago
Worth noting here is that the approximation factor here is 5500. (I.e., the algorithm is only guaranteed to return a route whose length is no more than 5500 times that of the optimal route.) Much bigger than 3/2! But apparently it's the first polynomial-time constant-factor approximation algorithm at all for it, so...