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 (Xiamen), China on 4 Feb 1931, the eldest son of Shui-Hsian Wang and Chio-Shih Lin.[5] He had a younger brother (born ~1932) and sister (born ~1939).[6] His family emigrated to the Philippines before World War II during the American colonial period where the lived in Quezon City.[6] He studied at University of the Philippines where his father Chio-Shih Lin was an associate professor (since 1939)[6] and earned his BS in Math there in 1951.[5] He came to the United States in 1952 to study at Ohio State University where he took graduate courses alongside his father[6] and earned a PhD in Math in 1963 under Tibor Radó. He worked at at Bell Labs starting in Oct 1963.[5]
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.[5]
He was president of the OSU Chess Club and qualified for the second team on the National Intercollegiate ping pong in 1954.[5]
References
- ↑ 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
- ↑ 5.0 5.1 5.2 5.3 5.4 Autobiography included in his PhD dissertation.
- ↑ 6.0 6.1 6.2 6.3 Mary Alice Richardson. "Father, Son Study Here". The Lantern. 26 May 1954. Page 7.
- Gina Kolata. Math Problem, Long Baffling, Slowly Yields. The New York Times. 12 Mar 1991. Section C. Page 1.