APSP +2 fast
[01-14-24]
I realized that I have very few blog posts with the tag "approximation algorithms". Seeing as I had recently heard this algorithm for APSP approx I thought I'd write it down.
approx tsp
[tsp]
Travelling Salesman Problem (TSP) is one of the most famous NP-hard problems. Today, we are going to solve it really fast! (well, really just approximate it to within a factor of 1.5, but still).