Sophia Heimann

According to our database, Sophia Heimann authored at least 3 papers between 2024 and 2026.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of four.

2026

On the PLS-Completeness of k-Opt Local Search for the Traveling Salesman Problem.

Sophia Heimann, Hung P. Hoang, Stefan Hougardy

CoRR, March, 2026

A Near-Complete Resolution of the Exponential-Time Complexity of k-opt for the Traveling Salesman Problem.

Sophia Heimann, Hung P. Hoang, Stefan Hougardy

Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, 2026

2024

The k-Opt Algorithm for the Traveling Salesman Problem Has Exponential Running Time for k ≥ 5.

Sophia Heimann, Hung P. Hoang, Stefan Hougardy

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024