我经常在近似算法中看到n^O(1/ε)。例如,在欧几里得TSP问题中,门户(及其可能的状态)的数量等于n^O(1/ε)。
这是源链接http://algo2.iti.kit.edu/schultes/lebenslauf/publications/euclTSPsummary.pdf
有人能解释一下为什么3^4m = n^O(1/ε)吗?
我经常在近似算法中看到n^O(1/ε)。例如,在欧几里得TSP问题中,门户(及其可能的状态)的数量等于n^O(1/ε)。
这是源链接http://algo2.iti.kit.edu/schultes/lebenslauf/publications/euclTSPsummary.pdf
有人能解释一下为什么3^4m = n^O(1/ε)吗?