Should be reading more and writing less, but well...

Saturday, April 02, 2005


Traveling Salesman

The traveling salesman problem (TSP) is a very simple combinatorial optimization problem. Given a set of cities and distances between each pair, the problem is to find the tour of least distance that travels each city exactly once. Simple - as in simple to state. But from what I have seen this seems to be the hardest of the hard problems to solve.

To give some background, there are these famous hard problems in Computer Science that do not have "efficient" solutions. Brute force solutions work very easily on them, but take an eternity to run. In spite of 40 years of extensive research by some very smart people, brute force seems to be the only solution. For example, the TSP can be solved by listing all possible tours covering the cities once, and picking the one with the least length. This takes an eternity as there are an exponential number of such tours (n!). These problems are the (in)famous NP-Hard problems. Stephen Cook at the University of Toronto proved that if one of them can be solved efficiently, all of them can be!!! A very intuitively pleasing fact.

Tragically, most combinatorial optimization problems in nature turn out to be NP-hard. As 40 years of research hasn't found a good solution to these problems, people have begun to approximate the solutions. Say, for TSP, if the least length best tour is around 100 KM, a procedure that finds a tour of 150 KMS would be considered good. Of course, if the length of the best tour is around 5000 KM, the same procedure should return a tour of length 7500 KM. This means that the approximate procedure for TSP should return a solution that is always some fixed fraction times more than the best solution. Most of the NP-hard problems have reasonable approximation algorithms; the TSP does not!!

It is proven that you cannot invent a procedure that can take a set of cities and give a tour that will always be some fraction times more than the optimal solution. TSP seems to be very very very very hard. But of course, most of this theory would collapse if someone comes up with a good way to solve one NP-hard problem.

In spite of my being really really really bad at this academically, I am completely enamored by the theory of NP-completeness. Somehow this notion of possible but not-feasible seems to make it intriguing. It is incredibly fascinating to see how all NP-hard problems are closely related to each other, and solving one solves them all, but approximating one, doesn't approximate them all. Seductive!!

Reminds me of Dijkstra's famous quote - "Computer Science is as much about Computers as Astronomy is about Telescopes."


> To give some background, there are these famous hard problems in Computer Science .......

I have a basic doubt. Isn't TSP a mathematical problem.

> Dijkstra's famous quote - "Computer Science is as much about Computers

Was Dijkstra trying to promote the Computer "Science" brand ?? He was basically a mathematician :)) .. Does computer "science" really got to do with things which is beyond computers ??
This distinction between mathematics and computer science is vague. Computer Science could be applied mathematics. Mathematics could be a tool that is used in many domains, of which CS is one. Discrete Mathematics could be considered CS. But the distinction and about where we classify these problems doesn't take away the beauty of the problems themselves. So, if TSP were to be a mathematical problem, I am happy there as well.

Computer Science has something to do beyond abstract computers? Not much, I guess. But the quote referred to conventional computers I presume.
Amazing problems...

I guess a lot of true computer science does go into designing conventional computers too. Yet these machines are not upto the expectations of theoretical computer science.

I still takes ppl to come up with algorithms.

I guess we need to look at the purpose computers were designed for - to to automate solution to 'trivial' numerical/digital problems. By trivial I mean, actual numerical problems involving numbers, names etc. Computers have been excellent at this. In fact the evolution of computers has been on this plane itself. No doubt we have things like routers, DSPs and intelligent auction agents. But these are things that solve problems in communication, business and entertainment in a computational way. But since computers have become so widespread in application, we have come to mistake them for living things akin to us in smartness. But the intelligence of computers has evolved in ways very different from human intelligence. Moreover, humans can solve all mathematical problems computers can. Coz our brain has all the analog and digital ingredients to do so. For example, TSP. The algorithm to solve it is as human as it is digital. You give the algorithm to a boy and ask him to solve the TSP for a particular case. But computers are not capabale for all that humans are.
teju, why do you use the same adjective many many many times? ;-)

comments on comments:
TSP is a real-world problem, described in mathematical terms. Since algorithmic problems are expressed and solved with intuition in mathematics, it is a mathematical problem? I dont know. This will determine whether Dijsktra was a mathematician.

Dijkstra was by training a physicist, and by profession a "computer scientist" -- it is a trivia that when he had to write his profession on his marriage certificate, he wrote Computer scientist.

computer science really has gotto do things beyond computers, how does your telephone call get routed? we no longer use a grid to place telephone calls! there are many other implications of doing "computer science" (as opposed to the general interpretation of "computing science") to problems beyond computers.

However, the intended meaning of the quote at that time was to the mathematical nature of problems involved in computing, and not just the box on your desk (or the big room with tubes).

Post a Comment

<< Home


February 2004   July 2004   August 2004   September 2004   October 2004   November 2004   December 2004   January 2005   February 2005   March 2005   April 2005   May 2005   June 2005   July 2005   August 2005   September 2005   October 2005   November 2005   December 2005   January 2006   February 2006   March 2006   April 2006   May 2006   June 2006   July 2006   August 2006   September 2006   October 2006   November 2006   January 2007   April 2007   May 2007   June 2007   November 2007   December 2007   January 2008   March 2008   June 2008   February 2009   June 2009   February 2010   November 2010  

Quick index to blog-posts I like (from my personal website)

This page is powered by Blogger. Isn't yours? Statscounter is generating statistics of this page