- TSP
- input:
1. a graph adjacency matrix of distances
2. a budget $b$
- output:
- a tour which passes through all cities & has length $\leq$ $b$ & returns to starting point, if such a tour exists
- is [[NP Complete Problems |NP Complete]]
- has an approximation algorithm, the [[TSP OPT Approximation Algorithm]]
https://people.eecs.berkeley.edu/~vazirani/algorithms/chap8.pdf
https://stackoverflow.com/questions/49837125/confusion-about-np-hard-and-np-complete-in-traveling-salesman-problems