On 2026-01-02 13:44, matt.egyhazy--- via Boost wrote:
Some comments:
1) Christofides approximation algorithm does the 1.5x max solution with MST + min weight perfect matching. It is O(V^3). I would prefer to write faster algorithm/heuristic that scales better. I will perhaps look into Christofides and/or LK after I finish the greedy Nearest Neighbor.
Good. I will resume my efforts to solve 100,000 cities mona-lisa100K.tsp with 1,000USD prize money https://www.math.uwaterloo.ca/tsp/data/ml/monalisa.html on semester break mid February (age 60): https://github.com/Hermann-SW/RR I use Ruin and Recreate principle, next essential step is parallelization (either with OpenMP on my 192 core 8-socket server or with HIP and my AMD Instinct MI50 GPUs).
2) Thank you, I step through your implementation.
Not my implementation, but that of original author Morihiko Tamai. I linked to his work in ezxdisp repo README.
3) Besides graphviz (which is not interactive), I am not aware of a built-in way of creating an interactive UI like you describe. I see no reason why it couldn't be used with UI code separately though, seems very straight forward. Simply separate the UI and the graph code in a encapsulated way. Can probably be done with metric_tsp_approx as-is.
You are right, will be a good exercise to replace LK TSP code in ezxdisp example and use metric_tsp_approx instead. Regards, Hermann.