4 ms·

I'm actually going to support Wired's wording on this one. While it's possible to come up with a perfect solution to any specific instance of the traveling sal

by allwein 16y ago

I'm actually going to support Wired's wording on this one. While it's possible to come up with a perfect solution to any specific instance of the traveling salesman problem, it's the actual process of solving that instance, the algorithm, that's actually interesting. Remember, solving the traveling salesman problem is easy/trivial, it's finding the shortest/optimal path that's hard. And for that you need a good algorithm.

kragen 16y ago
There are several errors in your comment (and in Wired's wording). Computers don't normally come up with algorithms; programmers come up with algorithms. Using the algorithms we've come up with so far, TSP of the complete graph of 4000 points, or even Euclidean TSP of 4000 points, is intractable except in special cases. We don't have a proof that there's no tractable or efficient algorithm. We have evidence in the form of an NP-completeness proof, but although unlikely, it's possible that P=NP and there's an efficient algorithm for TSP. As far as we know, it's possible that a computer doing some kind of search for algorithms — genetic programming is the sexiest kind of search, but of course not the only one — could find such an algorithm. We just don't have any idea. One of the consequences of the unresolved status of the P=NP conjecture and the infancy of AGI is that we can make very few statements about the capabilities of yet-undiscovered algorithms, or how easy or hard they are to discover. > Remember, solving the traveling salesman problem is easy/trivial, it's finding the shortest/optimal path that's hard. You're quibbling about technicalities, and you happen to be wrong about them. Formally, TSP is a decision problem: whether there exists a path shorter than a given length L. That's not "easy/trivial". As far as we know, it's as hard as computing the shortest path. Maybe you're talking about finding a path covering all vertices, which is not "solving the traveling salesman problem".
- 9999 16y ago
  I don't understand why they're bringing the traveling salesman problem into this at all. The core problem Uber has to solve is simply to get one driver (of many) to the customer as fast as possible, not to determine the most efficient route between all of the customers.
  - kragen 16y ago
    It's not that simple. They need to figure out which assignment of drivers to customers maximizes some utility function. If they just send the closest available driver, that may degrade service for some other customer, or leave an important area of the city uncovered for the next unexpected call. It's not the same problem as TSP, but it's surely reducible to it, given the NP-completeness proof.
- allwein 16y ago
  First off, your original complaint was on the inclusion of the word "algorithm", and not the fact that they referenced supercomputers solving the problem. As such, I didn't address it since you didn't address it. >Formally, TSP is a decision problem: whether there exists a path shorter than a given length L. That's not "easy/trivial". Also, it is easy/trivial to solve the traveling salesman problem (Try all permutations using brute force search). It's just not easy/trivial to solve it quickly/efficiently.
modeless 16y ago
Supercomputers don't generate algorithms (at least not yet!). People generate algorithms; supercomputers run them. That's why Wired's quote is wrong. If you consider the solution to a single instance of the traveling salesman problem an algorithm then the quote makes sense, but that would be an unusual and obtuse usage of the word.

by allwein 16y ago

kragen 16y ago

There are several errors in your comment (and in Wired's wording). Computers don't normally come up with algorithms; programmers come up with algorithms. Using the algorithms we've come up with so far, TSP of the complete graph of 4000 points, or even Euclidean TSP of 4000 points, is intractable except in special cases. We don't have a proof that there's no tractable or efficient algorithm. We have evidence in the form of an NP-completeness proof, but although unlikely, it's possible that P=NP and there's an efficient algorithm for TSP. As far as we know, it's possible that a computer doing some kind of search for algorithms — genetic programming is the sexiest kind of search, but of course not the only one — could find such an algorithm. We just don't have any idea. One of the consequences of the unresolved status of the P=NP conjecture and the infancy of AGI is that we can make very few statements about the capabilities of yet-undiscovered algorithms, or how easy or hard they are to discover. > Remember, solving the traveling salesman problem is easy/trivial, it's finding the shortest/optimal path that's hard. You're quibbling about technicalities, and you happen to be wrong about them. Formally, TSP is a decision problem: whether there exists a path shorter than a given length L. That's not "easy/trivial". As far as we know, it's as hard as computing the shortest path. Maybe you're talking about finding a path covering all vertices, which is not "solving the traveling salesman problem".

9999 16y ago
I don't understand why they're bringing the traveling salesman problem into this at all. The core problem Uber has to solve is simply to get one driver (of many) to the customer as fast as possible, not to determine the most efficient route between all of the customers.
- kragen 16y ago
  It's not that simple. They need to figure out which assignment of drivers to customers maximizes some utility function. If they just send the closest available driver, that may degrade service for some other customer, or leave an important area of the city uncovered for the next unexpected call. It's not the same problem as TSP, but it's surely reducible to it, given the NP-completeness proof.
allwein 16y ago
First off, your original complaint was on the inclusion of the word "algorithm", and not the fact that they referenced supercomputers solving the problem. As such, I didn't address it since you didn't address it. >Formally, TSP is a decision problem: whether there exists a path shorter than a given length L. That's not "easy/trivial". Also, it is easy/trivial to solve the traveling salesman problem (Try all permutations using brute force search). It's just not easy/trivial to solve it quickly/efficiently.

modeless 16y ago

Supercomputers don't generate algorithms (at least not yet!). People generate algorithms; supercomputers run them. That's why Wired's quote is wrong. If you consider the solution to a single instance of the traveling salesman problem an algorithm then the quote makes sense, but that would be an unusual and obtuse usage of the word.