This:

Even if all the world’s fastest supercomputers were put to work, they couldn’t generate a perfect algorithm to solve this classic puzzle, which computer scientists call the traveling-salesman problem.

made me a bit sad; it's overcomplicating the description by introducing the word "algorithm", when just "generate a perfect solution to this classic puzzle" would have been so much simpler, and also actually correct.

I had read more Wired, this is where I would lament over how it used to be better, and chase kids off my lawn, I guess.

Sure it's a "popular" text, but when it's easier to be correct, I think it's a bit saddening. This is a quite central sentence in their description of Uber's algorithms, so I think they should have gotten it right.

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.

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".

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.

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.

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.

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.

An interesting thing about this is that they're still basically a taxicab service; they just have a better user interface and scheduling algorithm. While the disappearance of taxi stands and radio dispatcher squawks in favor of network servers and algorithms may highlight how much of our everyday infrastructure serves an informational rather than a purely logistical purpose, it's the small story here.

The bigger story is Craigslist ridesharing, and carpooling startups like Zimride, PickupPal, Carpool to School, and CarBuddy. In countries like the US, where the average car has something like 5 seats of which 1.2 are full on any given trip, taxi and bus services are only able to exist at all due to an market failure of truly mind-boggling proportions.

Any time you drive anywhere in a city, there's probably a reputable, trustworthy person or two within a couple of blocks who wants to go close to where you're going, at the same time. If you knew about them, you could go pick them up (the 80% of the time that you don't mind driving an extra couple of blocks), and magically your cost of driving would drop by half or two-thirds.

It's a good deal for the passengers, too, compared to a cab. If your cost is 50¢ per mile, they might pay 25¢ per mile, compared to some 90¢ per mile in a taxicab; and of course, as with Über, they can just walk outside as the distance meter on their phone approaches zero.

Transportation inefficiency isn't a market failure-- cab supply is deliberately limited by most cities, and the price a cab can charge is fixed by the city as well. Similarly, jitney buses or other forms of efficient private mass transport are completely outlawed. The government doesn't want private bus routes competing with its clunky, unionized services.

The empty seat problem in private cars is more of an issue with personal safety and the broad increase in crime over the past fifty years. Technology should help here, but the reason low-tech hitchhiking has all but disappeared is that it is not safe for the rider or the driver. This didn't used to be the case-- the boomer generation hitchhiked across the country to college, for example.

Fixed cab fares are a response to passengers' effective inability to negotiate cab fares. In general, while transport regulations benefit the incumbents to some degree by raising the barrier to entry (rather shockingly in the case of NYC taxi medallions), they are generally supported by the public for reasons of safety.

There hasn't actually been a "broad increase in crime over the past fifty years" in the US; consider http://www.disastercenter.com/crime/nccrimn.htm which shows that, in North Carolina, violent crime in general has nearly doubled over that time, and robbery has increased by a factor of six, but murder rates have halved. A similar trend is seen in San Diego http://www.sandiego.gov/police/stats/ — violent crime has quadrupled, robbery has barely doubled, and murder has halved. Furthermore, these overall trends have been far from monotonic; the crime peak in 1990–1992 is far worse than anything we've seen over the last 20 years.

And there are lots of countries where low-tech hitchhiking is very much alive, and crime is much higher in most of them than in the US.

I think the real reason for the change is economic: as people in the US got much richer, they preferred the safety of private cars, airplanes, and other public transport, to the cost savings of hitchhiking.

Regardless, that's a problem of information. You want to know if the person you're riding with has a record of trying to rob or rape previous drivers or passengers, or even leering at their tits.

"The empty seat problem in private cars is more of an issue with personal safety and the broad increase in crime over the past fifty years."

It's more of an issue of the American perception of danger, and the anti-hitchhiking laws passed as a result. Lots of people still hitchhike all across the US.

I'd say that the danger in picking up a random stranger as a passenger isn't really about the danger that they're going to try to kill you. There's any number of other ways it can go wrong. They can smell bad. They can talk loudly or offensively. They can start going off with their theory about how the Jews run the country through the freemasons. They can be drunk and throw up. They can wind down the window and scream obscenities at nearby women. They can... well, ask any taxi driver for stories about what the worst things random strangers can do to your car.

If I were going to pick up random strangers to disrupt my otherwise-peaceful me-time alone in my car, it'd have to have a big incentive, and being able to split the money I pay for gas just ain't it. Being a taxi driver is a sucky job, and I don't wanna do it in my spare time for cents per mile.

Hmm, you have a good point — aside from people in the US being paranoid about crime, they're also unbelievably intolerant, to the point that they're not comfortable around teenagers talking loudly, drunk people, or people with different political views.

I'm not sure you're in a position to be lecturing others about tolerance after a comment like that.

"Tolerance" is a noble concept in some sense. It means I respect the right of others to be stupid and annoying in the abstract, not necessarily in my passenger seat.

I'm a US citizen, and I don't claim to be an exception to our general lack of tolerance; I mean, I've been unreasonably annoyed at teenagers talking loudly, or people dropping cigarettes on the sidewalk, or making racist remarks, just like most people from the US. I'm just observing a fact.

As for "noble concepts", well, there's the kind of tolerance that's a "noble concept", and then there's the kind of tolerance that's an actual description of how some people behave toward other people, some of the time. Like, how Argentinians behave toward children, that people from the US don't. Or, for that matter, how Argentinians behave toward US tourists.

Turns out that there are real benefits to turning down your annoyance and smarter-than-thou attitude and digging folks who don't shop at the same supermarket you do. I can't always do it, but I'm glad when I can.

(By the way, when you complain about how awful it is to have to talk to someone who's stupid, you should consider how that would sound to someone who's a lot smarter than you are.)

Well that's great, but are we still talking about how folks don't want random strangers riding in their cars? Because I still don't want random strangers riding in my car, and I don't reckon that's in any way unreasonable.

I never said people from the US were unreasonable, just unbelievably intolerant. That's a matter of preference, and I don't think it makes sense to describe preferences as reasonable or unreasonable. It's like saying that it's unreasonable to have the flu or be short. Preferences aren't voluntary choices.

Now, combine this with autonomous cars about ten to twenty years hence, and you've got a recipe for a major sea change in how we get around. Just another example of why I think naively projecting 20 years into the future as if there will be no changes in anything is a foolish waste of time.

It seems like the biggest risk with this company is that they're effectively skirting laws designed to limit the sort of service they're providing.

How long before cities up their rent-seeking and require all hired transportation to have a medallion?

They're not skirting the laws at all. The hiring of privates cars, limos, or buses is usually not restricted or regulated by cities.

The innovation here, and the reason the cab companies are up in arms about it, is that it's now on-demand hiring of private cars via phone. The cab companies used to have a lock on on-demand hiring via handwave or cabstanding.

"Skirting" was a poor choice of word on my part. I didn't mean to imply they were doing anything unethical or borderline.

I simply wanted to point out that regulating cab companies and selling expensive permits is a source of city revenue. If an innovative new business disrupts that revenue, it may quickly find itself the subject of new regulation.

Now, if their success is based on efficient routing algorithms and higher-class service, then they have nothing to worry about. If it's based on the fact that they don't have one of the cab companies' major expenses, then they're at significant risk of being regulated out of profitability.

These awesome new services are threat to the current monopoly providers, who are in league with the city and protected from competition by city laws. I guarantee that that many jurisdictions will attempt to outlaw, control, or license these services. They will claim the need for "safety regulations" or similar. And a lot of cities do restrict private car and bus services-- try setting up a regular bus route in your hometown. Where I live, the major Dulles Airport even limits outbound cab service to a single provider!

http://greatergreaterwashington.org/post/2920/time-to-ground...

Thats how you push the envelope. Airbnb has at various points run into headlines about similar issues but they have done an outstanding job delivering a product that people want in the real world. If a large number of people find value in the product then mostly governments and regulation come around (recreational drugs are an interesting but offtopic exception).

"It seems like the biggest risk with this company is that they're effectively skirting laws designed to limit the sort of service they're providing."

Personally I'd call that innovation. Clearly they're providing a service where there is demand. The law seems to be inadequate, so at the very least they're highlighting a problem for lawmakers to pay attention to.

Lawmakers do pay attention, existing monopoly arrangements are deals for specific companies and/or unions that support them. You are assuming that lawmakers always have the broad community's best interest at heart.

Full, unpaged version: http://www.wired.com/gadgetlab/2011/04/app-stars-uber/all/1

Perhaps I'm spoiled by living in NYC, but I don't see a way that this could actually work here.

San Francisco is a notoriously awful place to catch a cab, but I hardly see how taking advantage of a local policy/market failure represents something that might be disruptive to a whole industry... particularly at a 40% mark-up.

As a New Yorker, I'd have to agree. There already seems to be a glut of taxis for most times of the day (in addition to the higher-end sedans that very few people use).

Even here in Brooklyn, where hailing a cab is more difficult than in the city, calling a car service is super fast and not much more expensive than a yellow cab.

Arecibo (car service) almost always arrives within 5 minutes, and on numerous occasions I've had them say "ok, they're downstairs already" while still on the phone with them.

Not really a problem in need of solving in NYC, although it certainly will be interesting to see how it is received here.

Are you kidding? Pressing a button is way easier and faster than calling a person and telling them where you are. Seeing the fare and paying it on your phone before even reaching the destination is way better than settling with the driver using cash or credit cards while sitting in the car at your destination. This is a far better experience than calling a normal cab service.

Yeah, it doesn't make things so much easier that i'd pay more for it. The process is about 10 seconds right now, and settling up payment is easy if you're not a tourist in NY. It'd be one thing if it was a frustrating experience, but to be honest it's pretty easy already.

Plus I'm sure the car services are going to be resistant to the fees associated with it, changing their work flow, and are thinking about all the income I'm sure they don't declare. Actually, I just remembered this article from a while back about the car services: http://nymag.com/news/features/54678/

But sure, maybe someday I'll tap a screen to take care of it once we hit a quorum of use, I have no opposition to it. It just doesn't seem to be a problem in my life that needs solving. Yet another third party trying to get in between the transaction to skim some money off.

40% better?

DC actually does not cap the number of cabs (only the price they can charge) so there's pretty good supply here too. But I would definitely use Uber at peak times, though, like New Years or late-night or when it is raining.

I don't see any particular reason why this service would have to remain at a 40% markup in perpetuity. That's just where the sweet spot is right now.

Apple's rules are restricted to subscriptions and in-app purchases of virtual goods. They currently have no stance on purchases of real goods. See the Amazon App, Pizza Hut app, etc. for examples.

They actually have a hard stance that you cannot use in-app payments to pay for real goods.

NYC is unique in the US.

Excellent, the more things we're making more efficient with math, the better. If the pricing proves to be a huge hurdle I think they should try a subscription based model as well, and/or selling rides in bulk for cheaper.

How uber is the experience if you cannot get the cab on Halloween because it's $500(or $x) and you cannot afford it?

That's a STRONG price signal that will bring more cabs into the marketplace at peak times. $500 fares won't happen often or for very long-- I'd fire up my own ride and pick you up for $250!

That's a cool idea of crowdsourcing peak times. You sign up to get texts when people are willing to pay for rides above a certain threshold and then just drive your car out to pick them up.

I'd use it (and possibly do it, although hard to say and it'd have to be for a ridiculous amount of money ~100+ range/trip).

There would need to be a reputation component like airbnb; otherwise, you would run the risk of shady people picking you up knowing that you have >= $x dollars on you and steal it.

According to the article payment is handled via credit cards in the backend so you could have $0 on hand. Your broader point definitely still stands.

The heat map on page 2 is pretty interesting

Paging tptacket - our resident taxi expert!