Tayzwi
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 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."
Labels: computer science
posted by Tejaswi # 6:27 AM 
Comments:
<< Home
> 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 ??
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.
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.
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:
Direkishore,
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).
B
Post a Comment
comments on comments:
Direkishore,
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).
B
# posted by 
: 1:05 AM
: 1:05 AM<< Home
Archives
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)
