Рекомендовать хорошую эвристику для самого длинного гамильтонова пути за полиномиальное время

Question

У меня есть полный взвешенный граф с 1000 узлами, и мне нужно найти максимально длинный гамильтонов путь в графе (точнее, последовательность узлов). Я должен уместиться в 5 секунд (для Java), ограничение памяти достаточно велико. Поиск самого длинного гамильтонова пути мало чем отличается от поиска решения для TSP (коммивояжера). Конечно, об оптимальном решении не может быть и речи, поэтому я ищу хорошую эвристику. Моим лучшим решением на данный момент является использование алгоритма Nearest Neighbor, который прост в реализации и выполняется за полиномиальное время (занимает ~0,7 секунды для графа 1000 узлов). Это немного далеко от оптимального решения. Поэтому я ищу лучшую эвристику, которая все еще работает относительно быстро. Я вижу упомянутый поиск Табу, Имитация отжига, Муравьиная колония, Генетика, Ветвление и связывание, алгоритмы на основе MST и другие. Проблема в том, что их реализация не совсем тривиальна, трудно найти их временную сложность, чтобы решить, что может уместиться в 5 секунд. лимит времени; например, запустить в полиномиальное время. Для некоторых алгоритмов, таких как Christofides', я вижу, что сложность O(V^4), где V - число вершин, что, очевидно, делает невозможным подгонку.

Я наткнулся на решение Bitonic Tour, обычно используемое для нахождения кратчайшего гамильтонова пути в евклидовых графах, но, похоже, тоже неплохо для нахождения самого длинного пути в неевклидовых графах:

    public static void minCostTour(int[][] graph) {
        int n = graph.length;
        int[][] dp = new int[n][n];
        dp[0][1] = graph[0][1];

        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++)
                if (i == (j - 1) && i != 0) {
                    dp[i][j] = dp[0][j-1] + graph[0][j];
                    for (int k = 1; k <= j - 2; k++)
                        if ((dp[k][j-1] + graph[k][j] < dp[i][j])) { 
                            dp[i][j] = dp[k][j-1] + graph[k][j];
                        }
                } else if (i != 0 || j != 1) {
                    dp[i][j] = dp[i][j-1] + graph[j-1][j];
                }
        }
        System.out.println("Optimal Tour Cost: " + (dp[n-2][n-1] + graph[n-2][n-1]));
    }

Стандартный алгоритм включает начальную сортировку координат, которую я пропустил, так как, по-видимому, нет координат для сортировки (график неевклидов). Это решение динамического программирования работает в O(V^2), так что это может быть хорошо. Проблема в том, что он выводит длину пути гамильтониана, и мне нужна последовательность узлов. Я не могу понять, как восстановить путь из приведенного выше алгоритма (если это вообще возможно).

Версия TL DR: Можно ли использовать описанный выше алгоритм Bitonic Tour для нахождения последовательности узлов на самом длинном гамильтоновом пути в полном взвешенном графе? Если нет, можете ли вы порекомендовать алгоритм с аналогичной (полиномиальной) временной сложностью для этой задачи?