Shen Lin: Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
← Older editNewer edit →
VisualWikitext
→Bibliography: Add a couple more articles
RobinCodes (talk | contribs)
318 edits
m →Personal Life: Small grammar fix
Line 10: Line 10:


== Personal Life ==
== Personal Life ==
Shen Lin was born in Amoy ([[wikipedia:Xiamen|Xiamen]]), China on 4 Feb 1931, the eldest son of Shui-Hsian Wang and Chio-Shih Lin.<ref name="autobio">Autobiography included in his PhD dissertation.</ref> He had a younger brother (born ~1932) and sister (born ~1939).<ref name="lantern" /> His family emigrated to the Philippines before World War II during the [[wikipedia:History_of_the_Philippines_(1898–1946)|American colonial period]] where the lived in [[wikipedia:Quezon_City|Quezon City]].<ref name="lantern">Mary Alice Richardson. "[https://osupublicationarchives.osu.edu/?a=d&d=LTN19540526-01.2.52 Father, Son Study Here]". [[wikipedia:The_Lantern|The Lantern]]. 26 May 1954. Page 7.</ref> He studied at [[wikipedia:University_of_the_Philippines|University of the Philippines]] where his father Chio-Shih Lin was an associate professor (since 1939)<ref name="lantern" /> and earned his BS in Math there in 1951.<ref name="autobio" /> He came to the United States in 1952 to study at Ohio State University where he took graduate courses alongside his father<ref name="lantern" /> and earned a PhD in Math in 1963 under Tibor Radó. He worked at at Bell Labs starting in Oct 1963.<ref name="autobio" />
Shen Lin was born in Amoy ([[wikipedia:Xiamen|Xiamen]]), China on 4 Feb 1931, the eldest son of Shui-Hsian Wang and Chio-Shih Lin.<ref name="autobio">Autobiography included in his PhD dissertation.</ref> He had a younger brother (born ~1932) and sister (born ~1939).<ref name="lantern" /> His family emigrated to the Philippines before World War II during the [[wikipedia:History_of_the_Philippines_(1898–1946)|American colonial period]] where they lived in [[wikipedia:Quezon_City|Quezon City]].<ref name="lantern">Mary Alice Richardson. "[https://osupublicationarchives.osu.edu/?a=d&d=LTN19540526-01.2.52 Father, Son Study Here]". [[wikipedia:The_Lantern|The Lantern]]. 26 May 1954. Page 7.</ref> He studied at [[wikipedia:University_of_the_Philippines|University of the Philippines]] where his father Chio-Shih Lin was an associate professor (since 1939)<ref name="lantern" /> and earned his BS in Math there in 1951.<ref name="autobio" /> He came to the United States in 1952 to study at Ohio State University where he took graduate courses alongside his father<ref name="lantern" /> and earned a PhD in Math in 1963 under Tibor Radó. He worked at at Bell Labs starting in Oct 1963.<ref name="autobio" />


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.<ref name="autobio" />
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.<ref name="autobio" />

Revision as of 21:06, 4 December 2025

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 they 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]

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

  1. ↑ Shen Lin. 1963. Computer studies of Turing machine problems. PhD dissertation. Ohio State University. [1]
  2. ↑ 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
  3. ↑ 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
  4. ↑ D. E. Knuth. 1974. A terminological proposal. SIGACT News 6, 1 (January 1974), 12–18. doi:10.1145/1811129.1811130
  5. ↑ 5.0 5.1 5.2 5.3 5.4 Autobiography included in his PhD dissertation.
  6. ↑ 6.0 6.1 6.2 6.3 Mary Alice Richardson. "Father, Son Study Here". The Lantern. 26 May 1954. Page 7.
Retrieved from "https://wiki.bbchallenge.org/w/index.php?title=Shen_Lin&oldid=5348"