This was bothering me for a while because trivial algorithms like the nearest-neighbor or greedy algorithm heuristics have a complexity of O(n2) whereas they're claiming this is a linear time...
This was bothering me for a while because trivial algorithms like the nearest-neighbor or greedy algorithm heuristics have a complexity of O(n2) whereas they're claiming this is a linear time solution? How is that possible?
It finally occurred to me that they are "cheating" by calling it linear time when it's really more analogous to n parallel processes running in linear time, or perhaps, given that it requires n x n channels, maybe the better analogy is n2 processes in constant time. Either way, it's really O(n2) just like the trivial heuristics. Note that nearest-neighbor can be easily parallelized as well, so this "linear time" approximation is nothing new.
It is interesting though. I'd love to see how it fares compared to trivial heuristics in terms of approximation quality when increasing the number of cities and testing with different inter-city distance distributions.
Obligatory link to the complexity zoo for those who want to know what NP-hard means. :)
This was bothering me for a while because trivial algorithms like the nearest-neighbor or greedy algorithm heuristics have a complexity of O(n2) whereas they're claiming this is a linear time solution? How is that possible?
It finally occurred to me that they are "cheating" by calling it linear time when it's really more analogous to n parallel processes running in linear time, or perhaps, given that it requires n x n channels, maybe the better analogy is n2 processes in constant time. Either way, it's really O(n2) just like the trivial heuristics. Note that nearest-neighbor can be easily parallelized as well, so this "linear time" approximation is nothing new.
It is interesting though. I'd love to see how it fares compared to trivial heuristics in terms of approximation quality when increasing the number of cities and testing with different inter-city distance distributions.