Daily Archive for February 6th, 2008

Tavelling Salesman Problem (TSP) in Google Maps


What is TSP?

The travelling salesman problem (TSP) is a problem in discrete or combinatorial optimization. It is a prominent illustration of a class of problems in computational complexity theory which are classified as NP-hard.

neues-bild.png

Imagine you are a salesperson and have to visit a number of customers. However, you want to spend as little time as possible driving. If you only have to visit two or three locations, it is usually easy to find the optimal route. You can use regular map services such as Google Maps, Yahoo! Maps or MapQuest to find the shortest path between two places. However, as the number of locations to visit grows, the task of finding the order in which to visit the locations becomes daunting.

Continue reading ‘Tavelling Salesman Problem (TSP) in Google Maps’

Share and Enjoy:
  • Digg
  • del.icio.us
  • Facebook
  • Mixx
  • Google
  • Furl
  • Live
  • NewsVine
  • Reddit
  • StumbleUpon
  • Technorati
  • TwitThis
  • BlinkList
  • Fleck
  • Internetmedia
  • Ma.gnolia
  • MisterWong
  • description
  • Slashdot
  • Yigg
  • E-mail this story to a friend!

Google Doesn’t Know Where You Are (But It Has a Good Guess)


The following post is an excerp of a news paper article about Google’s My Location Service, which was recently introduced and is now in beta.

Users of Blackberries and many other smartphones can now push a button and the Google mapping service will figure out more or less sort of where they are.

Google recently added a feature for some smartphones that don’t have built in GPS but can read the unique identifying number of the cell tower they are connected to (This technique is called cell tower positioning, there exists also ther methods like WiFi Positioning Systems (WPS)). By using this information, Google can display a map of the general area they are in. (Google isn’t the first to try this sort of thing.)

Google nicely tried to design the service to take into account its limitations. When you push the button, it draws a dot at the nearest cell tower and draws a circle around it to identify the area in which it thinks you are. The screen will tell you the margin of error, typically between 500 and 2000 feet.

How does it work?

First, Google figures out which cell towers are where by secretly enlisting the help of a million of its mobile maps users who happen to have phones with built-in GPS devices that are not locked by the carriers. These phones have been reporting to Google where they are, based on the GPS data and what cell tower they are connected to.

Google stated that they had thought through the rather creepy privacy implications of all this. Google’s standard approach is that it logs everything it does by the unique cookie of an Internet browser (or the equivalent unique ID of a mobile phone). For the location information from GPS and cell towers, Google has built a database with not a bit of personal user information, they say.

When pressed, however, he also admitted there is a loophole to this. The payoff for Google from building out its mapping service is to get people to conduct searches from their cellphones. This is a nice feature. Push a button on the map software, type “Starbucks” and it will display a map of the closest source of a latte fix, based on the cell tower or GPS data. The catch, is that this query, with your location, is entered in Google’s log files along with your phone’s unique ID.

For almost everyone, this won’t matter. But if your location is really a secret, don’t ask Google to help you find coffee.

Some reactions from Google according this NYT article:

bart.gif

UPDATE: Barry Schnitt, of Google’s PR department, wrote with some clarifications. The service, he said, is in beta and the accuracy will improve as it is used. He took issue with the word “secretly” about how Google gathers the GPS data because such use is disclosed in the privacy policy of the service. And he also doesn’t like the headline that implies that Google has a good guess where you are. Google, as the item says, knows your cellphone’s ID number but not your name.

UPDATE 2: Mr. Schnitt wrote back to say I was wrong and that the unique ID used by the Google Maps system can’t be connected to any ID for GMail, which uses a separate application. So unless the map application starts to ask you to identify yourself, Google doesn’t know where you are.

[New York Times Article, 28.11.2007]

Written and submitted from Home, using my 802.11g WiFi network.

Share and Enjoy:
  • Digg
  • del.icio.us
  • Facebook
  • Mixx
  • Google
  • Furl
  • Live
  • NewsVine
  • Reddit
  • StumbleUpon
  • Technorati
  • TwitThis
  • BlinkList
  • Fleck
  • Internetmedia
  • Ma.gnolia
  • MisterWong
  • description
  • Slashdot
  • Yigg
  • E-mail this story to a friend!