Te Chiang Hu (Chinese: 胡德强, 1930–2021) was a Chinese-American computer scientist and operations researcher known for his work in the design and analysis of algorithms. His contributions to network flow problems included the representation of all pairwise flows using the Gomory–Hu tree,[GH61] the formulation of the multi-commodity flow problem,[H63] and a textbook on flow problems.[HY69][1] He also published highly cited algorithms for scheduling tree-structured tasks,[H61a] the widest path problem,[H61b] optimal binary search trees,[HT71] linear layouts of trees and graphs,[AH73] minimum routing cost spanning trees,[H74] and the matrix chain multiplication problem.[HS82]
Early life and education edit
Hu's family came from Zhejiang. Hu was born in 1930 in Beijing, and moved to Taiwan in the late 1940s as part of the retreat of the Republic of China to Taiwan following the defeat of the Kuomintang in the Chinese Civil War. He studied engineering at National Taiwan University, graduating with a bachelor's degree in 1953. He moved to the United States for graduate study, first earning a master's degree in 1956 at the University of Illinois Urbana-Champaign, and then completing a Ph.D. in 1960 at Brown University.[2] His doctoral dissertation, Optimum design for structures of perfectly-plastic materials, was supervised by Richard Thorpe Shield.[3]
Career and later life edit
After completing his doctorate, Hu worked for IBM Research from 1960 to 1966, also including consulting at the RAND Corporation.[2] It was during this period that he did much of his early work on network flow, including the development of the Gomory–Hu tree with Ralph E. Gomory.[GH61][2] In 1966, he took a faculty position at the University of Wisconsin–Madison, and in 1968 was named full professor of computer science. He published his book on network flow in 1969.[HY69][2]
In 1974 he moved to the University of California, San Diego, initially in the Applied Electro-Physics Department and later becoming a founding member of the Department of Computer Science and Engineering.[4] The Mathematics Genealogy Project lists eight doctoral students of Hu there, including Frank Ruskey.[3] He published another textbook on algorithms in 1982,[H82][2][5] and worked on the matrix chain multiplication problem with his student M. T. Shing (later added as a coauthor to his algorithms text) in the early 1980s.[HS82][6] He returned to the topic of his dissertation, the optimal design of surfaces, with a 1992 paper on finding minimal surfaces with nonzero thickness using network flow,[HKR92][7] and won a best-paper award for a 1995 paper on circuit partitioning.[L+95][2] He retired in 2007,[4] but continued publishing research; one of his last publications was a book on linear programming with another of his students, Andrew Kahng.[HK16]
He died in October 2021.[2]
Recognition edit
Hu was elected as a Fellow of the Institute for Operations Research and the Management Sciences (INFORMS) in 2013.[2] A special session of the 2018 International Symposium on Physical Design commemorated his contributions to the field.[8]
Selected works edit
Research papers edit
| H61a. | Hu, T. C. (1961), "Parallel sequencing and assembly line problems", Operations Research, 9: 841–848, doi:10.1287/opre.9.6.841, JSTOR 167050, MR 0135614
|
| H61b. | Hu, T. C. (1961), "The maximum capacity route problem", Operations Research, 9 (6): 898–900, doi:10.1287/opre.9.6.898, JSTOR 167055
|
| GH61. | Gomory, R. E.; Hu, T. C. (1961), "Multi-terminal network flows", Journal of the Society for Industrial and Applied Mathematics, 9: 551–570, MR 0135624
|
| H63. | Hu, T. C. (June 1963), "Multi-commodity network flows", Operations Research, 11 (3): 344–360, doi:10.1287/opre.11.3.344, JSTOR 168023
|
| HT71. | Hu, T. C.; Tucker, A. C. (1971), "Optimal computer search trees and variable-length alphabetical codes", SIAM Journal on Applied Mathematics, 21: 514–532, doi:10.1137/0121057, MR 0304063
|
| AH73. | Adolphson, D.; Hu, T. C. (1973), "Optimal linear ordering", SIAM Journal on Applied Mathematics, 25: 403–423, doi:10.1137/0125042, MR 0345618
|
| H74. | Hu, T. C. (1974), "Optimum communication spanning trees", SIAM Journal on Computing, 3: 188–195, doi:10.1137/0203015, MR 0427116
|
| HS82. | Hu, T.-C.; Shing, M.-T. (1982), "Computation of matrix chain products, I", SIAM Journal on Computing, 11 (2): 362–373, doi:10.1137/0211028, MR 0652909; ——; —— (1984), "Computation of matrix chain products, II", SIAM Journal on Computing, 13 (2): 228–251, doi:10.1137/0213017, MR 0739987
|
| HKR92. | Hu, T. C.; Kahng, A. B.; Robins, G. (October 1992), "Solution of the discrete Plateau problem", Proceedings of the National Academy of Sciences, 89 (19): 9235–9236, doi:10.1073/pnas.89.19.9235, PMC 50100
|
| L+95. | Liu, Lung-Tien; Kuo, Ming-Ter; Cheng, Chung-Kuan; Hu, T.C. (May 1995), "A replication cut for two-way partitioning", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 14 (5): 62–630, doi:10.1109/43.384426
|
Books edit
| HY69. |
| H82. | Hu, T. C. (1982), Combinatorial Algorithms, Addison-Wesley, ISBN 9780201038590; 2nd ed., with Man-Tak Shing, Dover, 2002
|
| HK16. | Hu, T. C.; Kahng, Andrew B. (2016), Linear and Integer Programming Made Easy, Springer International Publishing, doi:10.1007/978-3-319-24001-5, ISBN 9783319240015
|
References edit
- ^ Reviews of Integer Programming and Network Flows:
- Ellis Johnson, Bulletin of the AMS, doi:10.1090/S0002-9904-1978-14460-7
- Jaroslav Morávek, Mathematical Reviews, MR263420
- Joachim Piehler (in German), zbMATH, Zbl 0197.45701
- J. Terno (in German), ZAMM, doi:10.1002/zamm.19740540723
- S. Vajda, Journal of the Operational Research Society, doi:10.1057/jors.1970.122, JSTOR 3008450
- Ledelse og Erhvervsøkonomi (in Danish), [1]
- ^ a b c d e f g h "Hu, Te Chiang", Biographical profiles, INFORMS, retrieved 2023-11-30
- ^ a b T. C. Hu at the Mathematics Genealogy Project
- ^ a b "CSE Founder Retires", Department of Computer Science and Engineering, University of California, San Diego, archived from the original on 2007-06-08
{{citation}}: CS1 maint: unfit URL (link) - ^ Reviews of Combinatorial Algorithms:
- ^ Schwartz, Oded; Weiss, Elad (2019), "Revisiting 'Computation of matrix chain products'", SIAM Journal on Computing, 48 (5): 1481–1486, doi:10.1137/18M1195401, MR 4000229
- ^ Zamichow, Nora (October 1, 1992), "Floating an answer to bubble riddle: Science: Research team comes up with a solution to a 150-year-old brain teaser; the findings could have practical applications and lead to a new branch of math", Los Angeles Times
- ^ Kahng, Andrew B. (March 2018), "Influence of Professor T. C. Hu's works on fundamental approaches in layout", Proceedings of the 2018 International Symposium on Physical Design (ISPD '18), Association for Computing Machinery, doi:10.1145/3177540.3177563