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. 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 heuristic solutions to hard problems. He collaborated with Brian Kernighan on the Kernighan–Lin algorithm for graph partitioning. and the Lin–Kernighan heuristic for the traveling salesman problem. In a 2003 interview with Kernighan, he said:

I went back to Bell Labs the summer after that. This time, I got lucky and worked with Shen Lin, a great mathematician and problem solver. Shen was interested in hard combinatorial optimization problems, such as the Traveling Salesman Problem. I had been working in a casual way on what came to be called the graph partitioning problem for my Princeton thesis. Shen had an idea of how to attack the general case, and I made the algorithm work in a Fortran program. It became the core of my thesis, along with some other special cases.

In a 1974 article discussing terminology for what would eventually become known as NP-hard, Donald Knuth writes:

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. He had a younger brother (born ~1932) and sister (born ~1939). His family emigrated to the Philippines before World War II during the American colonial period where they lived in Quezon City. He studied at University of the Philippines where his father Chio-Shih Lin was an associate professor (since 1939) and earned his BS in Math there in 1951. He came to the United States in 1952 to study at Ohio State University where he took graduate courses alongside his father and earned a PhD in Math 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.

He was president of the OSU Chess Club and qualified for the second team on the National Intercollegiate ping pong in 1954.

Bibliography

• Shen Lin and Tibor Rado. 1965. Computer Studies of Turing Machine Problems. J. ACM 12, 2 (April 1965), 196–212. doi:10.1145/321264.321270
• S. Lin, "Computer solutions of the traveling salesman problem," in The Bell System Technical Journal, vol. 44, no. 10, pp. 2245-2269, Dec. 1965, doi:10.1002/j.1538-7305.1965.tb04146.x
• Hwang, F.K., Lin, S. Optimal merging of 2 elements with n elements. Acta Informatica 1, 145–158 (1971). doi:10.1007/BF00289521
• F. K. Hwang and S. Lin. 1972. A Simple Algorithm for Merging Two Disjoint Linearly Ordered Sets. SIAM Journal on Computing. Pages 31-39. doi:10.1137/0201004
• F. K. Hwang and S. Lin. 1973. Hypergeometric group testing algorithms. In Proceedings of the June 4-8, 1973, national computer conference and exposition (AFIPS '73). Association for Computing Machinery, New York, NY, USA, 452. doi:10.1145/1499586.1499700
• F.K Hwang, S Lin. A direct method to construct triple systems. Journal of Combinatorial Theory, Series A. Volume 17, Issue 1, 1974, Pages 84-94. doi:10.1016/0097-3165(74)90030-2
• S. Lin. 1975. Heuristic Programming as an Aid to Network Design. Netw. 5, 1 (January 1975), 33–43. doi:10.1002/net.1975.5.1.33
• F.K Hwang, S Lin. Neighbor designs. Journal of Combinatorial Theory, Series A, Volume 23, Issue 3, 1977, Pages 302-313. doi:10.1016/0097-3165(77)90021-8
• F.K. Hwang, S. Lin. Distribution of integers into k-tuples with prescribed conditions. Journal of Combinatorial Theory, Series A, Volume 25, Issue 2, 1978, Pages 105-116. doi:10.1016/0097-3165(78)90073-0
• Hwang, F.K. and Lin, S. (1979), On the construction of balanced switching networks. Networks, 9: 283-307. doi:10.1002/net.3230090402
• G.J. Chang, F.K. Hwang, S. Lin. Group testing with two defectives. Discrete Applied Mathematics, Volume 4, Issue 2, 1982, Pages 97-102. doi:10.1016/0166-218X(82)90067-1

References

• Gina Kolata. Math Problem, Long Baffling, Slowly Yields. The New York Times. 12 Mar 1991. Section C. Page 1.