Shen Lin
Shen Lin was an early Busy Beaver researcher. He was a graduate student of Tibor Radó at Ohio State University and solved BB(3) in his PhD dissertation there.[1] He was the first to describe Translated Cyclers (which he called "partial recurrence") and to publish an algorithm to detect them.
After graduating, he worked at Bell Labs where he researched heuristics for solving hard problems. Ex: the Lin–Kernighan heuristic for the traveling salesman problem[2] and the Kernighan–Lin algorithm for graph partitioning.[3] Both were co-authored with Brian Kernighan of K&R C fame.
Lin appears to have been drawn specifically to work on known hard problems in general. In a 1974 article discussing terminology for what would eventually become known as NP-hard, Donald Knuth writes:[4]
Shen Lin thought of calling them PET problems, as he likes to work on them (e.g. the traveling salesman problem) in spite of their difficulty. He points out that PET stands for "probably exponential time". But if this gets proved, PET stands for "provably exponential time". And if the proof goes the other way, it stands for "previously exponential time".
Personal Life
Shen Lin was born in Amoy, China on 4 Feb 1931, the eldest son of Shui-Hsian Wang and Chio-Shih Lin. His family emigrated to the Philippines before World War II. He graduated from the University of the Philippines in 1951 with a BS in Math. He came to the United States in 1952 and completed a PhD in Math from Ohio State University in 1963 under Tibor Radó. He worked at at Bell Labs starting in Oct 1963.
In 1956 he married Mona L. Lo in Columbus, Ohio and (as of 1963) they had 3 children: John (born ~1957), David (born ~1959) and Robert (born ~1961). He became a naturalized US citizen in 1961.[1]
References
- ↑ 1.0 1.1 Shen Lin. 1963. Computer studies of Turing machine problems. PhD dissertation. Ohio State University. [1]
- ↑ Lin, Shen; Kernighan, B. W. (1973). "An Effective Heuristic Algorithm for the Traveling-Salesman Problem". Operations Research. 21 (2): 498–516. doi:10.1287/opre.21.2.498
- ↑ Kernighan, B. W.; Lin, Shen (1970). "An efficient heuristic procedure for partitioning graphs". Bell System Technical Journal. 49 (2): 291–307. doi:10.1002/j.1538-7305.1970.tb01770.x
- ↑ D. E. Knuth. 1974. A terminological proposal. SIGACT News 6, 1 (January 1974), 12–18. doi:10.1145/1811129.1811130