(Add category)
Line 5: Line 5:
 
2. History (Hao Xu)
 
2. History (Hao Xu)
  
Chinese Postman Problem was discovered by a Chinese mathematician --- Kwan Mei-Ko. The problem described a situation that the Chinese postman would face everyday: How to travel along every road in a city to deliver letters while trying to finish the job in a minimum distance.  
+
During the Great Leap Forward movement period in the Chinese history (1958-1960), president Mao of China encouraged scientists to solve real-world problems in order to accelerate the transformation of economy mode of China. At that time, many mathematic researchers focused on problems like transportation and production planning. And Shandong province, as a center of early Chinese mathematic researches, is where Chinese Postman Problem was created. (Grotschel & Yuan).
 +
 
 +
Chinese Postman Problem was discovered by a Chinese mathematician --- Kwan Mei-Ko. The problem described a situation that the Chinese postman would face everyday. The exact problem was defined in Kwan's paper as, "A postman has to deliver letters to a given neighbourhood. He needs to walk through all the streets in the neighbourhood and back to the post-office. How can he design his route so that he walks the shortest distance?"
 +
 
 +
Then he converted this problem to a more generic one by counting the number of edges linked to a node as, "Given a connected graph where 2n of the nodes are odd and all other nodes are even. Suppose we need to add some edges to the graph with the following property: the number of edges added to any odd node is odd and that added to any even node is even. We need to minimize the total length of the added edges."
 +
 
 +
Then he solved this problem by his theorem, which is also in his paper,
 +
"For a set of added edges it is necessary and sufficient to be an optimal solution for the above problem if the following two conditions hold:
 +
1). Between any two nodes, no more than one edge is added,
 +
2). In any cycle of the extended graph, the total length of the added edge is not greater than half of the total length of the cycle."
  
 
3. Real World applications(Zexuan Zhou)
 
3. Real World applications(Zexuan Zhou)
Line 13: Line 22:
 
5. Examples(Hao Wu)
 
5. Examples(Hao Wu)
  
 +
 +
reference:
 +
 +
Kwan, M. K. (1960). Programming method using odd or even pints, ''Acta      Mathematica sinica'', 10, 263-266.
 +
 +
Grotschel, M., & Yuan, Y. X. (2010). Euler, Mei-ko Kwan, Konigsberg, and a Chinese postman. ''Documenta Math.'', 43-50.
  
 
[[Category:MA279Spring2016Walther]]
 
[[Category:MA279Spring2016Walther]]

Revision as of 00:43, 15 April 2016

Chinese postman problem

1. What it is/ How to sovlve. (Sargun)

2. History (Hao Xu)

During the Great Leap Forward movement period in the Chinese history (1958-1960), president Mao of China encouraged scientists to solve real-world problems in order to accelerate the transformation of economy mode of China. At that time, many mathematic researchers focused on problems like transportation and production planning. And Shandong province, as a center of early Chinese mathematic researches, is where Chinese Postman Problem was created. (Grotschel & Yuan).

Chinese Postman Problem was discovered by a Chinese mathematician --- Kwan Mei-Ko. The problem described a situation that the Chinese postman would face everyday. The exact problem was defined in Kwan's paper as, "A postman has to deliver letters to a given neighbourhood. He needs to walk through all the streets in the neighbourhood and back to the post-office. How can he design his route so that he walks the shortest distance?"

Then he converted this problem to a more generic one by counting the number of edges linked to a node as, "Given a connected graph where 2n of the nodes are odd and all other nodes are even. Suppose we need to add some edges to the graph with the following property: the number of edges added to any odd node is odd and that added to any even node is even. We need to minimize the total length of the added edges."

Then he solved this problem by his theorem, which is also in his paper, "For a set of added edges it is necessary and sufficient to be an optimal solution for the above problem if the following two conditions hold: 1). Between any two nodes, no more than one edge is added, 2). In any cycle of the extended graph, the total length of the added edge is not greater than half of the total length of the cycle."

3. Real World applications(Zexuan Zhou)

4. Variations (Evan)

5. Examples(Hao Wu)


reference:

Kwan, M. K. (1960). Programming method using odd or even pints, Acta Mathematica sinica, 10, 263-266.

Grotschel, M., & Yuan, Y. X. (2010). Euler, Mei-ko Kwan, Konigsberg, and a Chinese postman. Documenta Math., 43-50.

Alumni Liaison

Ph.D. on Applied Mathematics in Aug 2007. Involved on applications of image super-resolution to electron microscopy

Francisco Blanco-Silva