Tag · 3 problems · 2 fields

Open problems tagged tsp

3 problems in the Math Lab index touch tsp, spanning Algorithms & Simulation, Combinatorics. Each carries a precise statement, an honest status, and a computational line of attack.

Heuristics vs. exact methods on NP-hard problemsAlgorithms & Simulationuntouched

On specific graph families, how close do learned or AI-generated heuristics get to exact optima for max-cut, vertex cover, and TSP variants — and where exactly do they fail?

Minimal superpermutations — extended searchAlgorithms & Simulationuntouched

Push the computational frontier on shortest superpermutations: close the 867–872 gap at n = 6 and improve constructions for n = 7–8.

Superpermutation problemCombinatoricsuntouched

What is the shortest string over n symbols containing every permutation of them as a consecutive substring? Known exactly only for n ≤ 5.