T. C. Hu

Professor above-scale

Department of Computer Science and Engineering
University of California, San Diego
9500 Gilman Drive
La Jolla, CA 92093-0114

Email: hu@cs.ucsd.edu


http://www-cse.ucsd.edu/users/hu
Telephone: (831) 620-0586
Fax: (858) 534-7029

  • BIBLIOGRAPHY (Ps file) (PDF file) New

  • CAREER SUMMARY (Ps file) (PDF file) New

  • SHORT BIOGRAPHY

    EDUCATION

    • B.S. (Engineering) National Taiwan University 1953
    • M.S. (Engineering) University of Illinois 1956
    • Ph.D. (Applied Math.) Brown University 1960

    POSITIONS

    • 1954-1956 Programmer, University of Illinois
    • 1960-1966 Research Mathematician, IBM Research Center
    • 1964-1965 Visiting Associate Professor, Electrical Engineering and Operations Research Center, University of California, Berkeley (on leave from IBM)
    • 1965-1966 Adjunct Associate Professor, Columbia University (part-time)
    • 1966-1968 Associate Professor, University of Wisconsin
    • 1968-1974 Professor, Computer Sciences Department and Mathematics Research Center, University of Wisconsin-Madison
    • 1974-present Professor, Department of Computer Science and Engineering, University of California, San Diego

    OTHER ACTIVITIES

    • Associate Editor, Journal of SIAM
    • Associate Editor, Journal of ORSA
    • Consultant, RAND Corporation, Summer 1965
    • Consultant, Office of Emergency Preparedness, Exec. Office of the President, 1968-72
    • Editor, IEEE Transactions on Computers
    • Advisory Editor, Journal of Heuristics
    • Advisory Editor, Journal of Graphs and Applications

    RESEARCH INTERESTS

    • Combinatorial Algorithms
    • Mathematical Programming
    • Networks and Graphs
    • VLSI Circuit Layout

    MEMBERSHIP IN PROFESSIONAL SOCIETIES

    • ACM, SIAM, ORSA, Mathematical Programming, IEEE.

    RECENT INVITED LECTURES AND HONORS

    • Workshop on VLSI Layout Theory, Dagstahl, Germany, Sept. 9-11, 1991.
    • "Combinatorial Problems in VLSI," 16th International Symposium on Operations Research, Trier, Germany, Sept. 9-11, 1991.
    • Second ORSA Telecommunications Conference, Boca Raton, Florida, March 9-11, 1992, (90-minute tutorial).
    • Plenary lecture, 17th Symposium on Operations Research, Hamburg, Germany, Aug. 25-28, 1992.
    • Mathematische Optimierung, Mathematishes Forschungsinstitut Oberwolfach, Germany, January 8-14, 1995.
    • John von Neuman Professorship, University of Bonn, Germany, 1994-95.
    • Senior Professor, Fulbright, 1994-95.
    • Keynote address, 1st International Symposium on Physical Design, April 14-16, 1997, Napa Valley CA.
    • IEEE Circuits and Systems Society, Best Paper Award, 1997.

    PUBLICATIONS

    Books

    • Integer Programming and Network Flows, by T. C. Hu, published by Addison-Wesley, 1969. Translated into German by H. P. Kunzi and G. Uebe, published by Oldenbourg Verlag, 1972. Translated into Russian, published by Mir, 1974. Translated into Japanese by Mr. Iri H. Konn and T. Tanahashi, published by Baifukan, 1975.
    • Mathematical Programming, edited by T. C. Hu and S. M. Robinson, Academic Press, 1973.
    • Combinatorial Algorithms, by T. C. Hu, Addison-Wesley, 1982.
    • Theory and Concepts of Circuit Layout, edited by T. C. Hu, and E. S. Kuh, IEEE Press, 1985.

    Chapters in Books

    • "Some Results and Problems in Binary Trees," by T. C. Hu, in Combinatorial Algorithms, edited by Randall Rusting, Algorithmics Press, 1973.
    • "Multi-Terminal Flows in a Network," by R. E. Gomory and T. C. Hu, in Studies in Graph Theory, Part I, edited by D. R. Fulkerson, volume 11 of the MAA Studies in Mathematics, the Mathematical Association of America, 1975.
    • "Computational Complexity of Layout Problems," by M. T. Shing and T. C. Hu, Chapter 8 of Layout Design and Verification, edited by T. Ohtsuki, volume 4 of Advances in CAD for VLSI, North-Holland, 1986.

    Papers in Journals

    • 1. "Network Analysis of Production Smoothing," by T. C. Hu and W. Prager, Naval Research Logistics Quarterly, Vol. 6, No. 1, 1959, pp. 17-23.
    • 2. "Uniqueness in the Optimum Design of Structures," T. C. Hu and R. T. Shield, Transactions of the ASME: Journal of Applied Mechanics, Vol. 28, No. 2, 1961, pp. 284-287.
    • 3. "Minimum-Volume Design of Discs," T. C. Hu and R. T. Shield, Zeitschrift fur Angewandte Mathematik und Physik, Vol. 12, No. 5, 1961, pp. 414-433.
    • 4. "Parallel Sequencing and Assembly Line Problems," T. C. Hu, Operations Research, Vol. 9, No. 6, 1961, pp. 841-848.
    • 5. "The Maximum Capacity Route Problem," T. C. Hu, Operations Research, Vol. 9, No. 6, 1961, pp. 898-900.
    • 6. "Multi-Terminal Network Flows," R. E. Gomory and T. C. Hu, Journal of SIAM, Vol. 9, No. 4, 1961, pp. 551-570. (Honorable Mention as an outstanding paper in 1961 by Operations Research Society.)
    • 7. "An Application of Generalized Linear Programming to Network Flows," R. E. Gomory and T. C. Hu, Journal of SIAM, Vol. 10, No. 2, 1962, pp. 260-283.
    • 8. "Multi-Commodity Network Flows," T. C. Hu, Operations Research, Vol. 11, No. 3, 1963, pp. 344-360.
    • 9. "Analysis and Synthesis of Communication Networks," R. T. Chian, R. E. Gomory and T. C. Hu (Invited Survey), IEEE Transactions on Circuit Theory, 1964, CT-11, No. 1, pp. 19-22.
    • 10. "Synthesis of a Communication Network," R.E. Gomory and T. C. Hu, Journal of SIAM, Vol. 12, No. 2, 1964, pp. 348-369.
    • 11. "On the Feasibility of Simultaneous Flows in a Network," T. C. Hu, Operations Research, Vol. 12, No. 2, 1964, pp. 359-360.
    • 12. "Minimum-Cost Flows in Convex Cost Networks," T. C. Hu, Naval Research Logistics Quarterly, Vol. 13, No. 1, 1966, pp. 1-9.
    • 13. "Decomposition in Traveling Salesman Type Problems," T.C. Hu, Proceedings of IFORS, Session A, Theory of Graphs, pp. A-34-A-44, 1966.
    • 14. "Laplace's Equation and Network Flows," T. C. Hu, Operations Research, Vol. 15, No. 2, 1967, pp. 348-356.
    • 15. "Revised Matrix Algorithms for Shortest Paths," T. C. Hu, SIAM Journal on Applied Mathematics, Vol. 15, No. 1, 1967, pp. 207-218.
    • 16. "A Decomposition Algorithm for Shortest Paths in a Network," T. C. Hu, Operations Research, Vol. 16, No. 1, 1968, pp. 91-102.
    • 17. "Recent Advances in Network Flows," T. C. Hu, SIAM Review, Vol. 10, No. 3, 1968, pp. 354-359.
    • 18. "Shortcut in the Decomposition Algorithm for Shortest Paths in a Network," T. C. Hu and W. T. Torres, IBM Journal of Research Development, Vol. 13, No. 4, 1969, pp. 387-390.
    • 19. "On the Asymptotic Integer Algorithm," T. C. Hu, Linear Algebra and its Applications, Vol. 3, No. 3, 1970, pp. 279-294.
    • 20. "Optimal Computer Search Trees and Variable-Length Alphabetical Codes," T. C. Hu and A. C. Tucker, SIAM Journal on Applied Mathematics, Vol. 21, No. 4, 1971, pp. 514-532.
    • 21. "Path Length of Binary Search Trees," T. C. Hu and K. C. Tan, SIAM Journal on Applied Mathematics, Vol. 22, No. 2, 1972, pp. 225-234.
    • 22. "Some Problems in Discrete Optimization," T. C. Hu, Mathematical Programming, Vol.1, No. 1, 1971, pp. 102-112.
    • 23. "A Comment on the Double-Chained Tree," T. C. Hu, Communications of ACM, Vol. 15, No. 4, 1972, p. 276.
    • 24. "Least Upper Bound on the Cost of Optimum Binary Search Trees," T. C. Hu and K. C. Tan, ACTA Informatiica Vol. 1, 1972, pp. 307-310.
    • 25. "A New Proof of the T-C Algorithm," T. C. Hu, SIAM Journal on Applied Mathematics, Vol. 25, No. 1, 1973, pp. 83-94.
    • 26. "Some Results and Problems in Binary Trees," by T. C. Hu, in Combinatorial Algorithms, edited by Randall Rustin, Algorithmics Press, 1973, pp. 11-15.
    • 27. "Multi-Terminal Flows in a Network," by R. E. Gomory and T. C. Hu, in Studies in Graph Theory, Part I, edited by D. R. Fulkerson, Vol. 11 of the MAA Studies in Mathematics, The Mathematical Association of America, 1975, pp. 172-199.
    • 28. "Two-Commodity Cut-Packing Problem," T. C. Hu, Mathematical Programming, Vol. 4, No. 1, 1973, pp. 108-109.
    • 29. "Optimal Linear Ordering," D. Adolphson and T. C. Hu, SIAM Journal on Applied Mathematics, Vol. 25, No. 3, 1973, pp. 403-423.
    • 30. "R-Separating Sets," R. E. Gomory, T. C. Hu and J. M. Yohe, Canadian Journal of Mathematics, Vol. 26, No. 6, 1974, pp. 1418-1429.
    • 31. "Optimum Communication Spanning Trees," T. C. Hu, SIAM Journal on Computing, Vol. 3, No. 3, 1974, pp. 188-195.
    • 32. "Shortest String Containing All Permutations," P. J. Koutas and T. C. Hu, Discrete Mathematics, Vol. 11, 1975, pp. 125-132.
    • 33. "Optimality of a Heuristic Solution for a class of Knapsack Problems," T. C. Hu and M. Lenard, Operations Research, Vol. 24, No. 1, 1976, pp. 193-196.
    • 34. "Generating Permutations with Nondistinct Items," T. C. Hu and B. N. Tien, American Mathematical Monthly, Vol. 83, No. 8, 1976, pp. 629-631.
    • 35. "Tree Decomposition Algorithm in Large Networks," W. Blewett and T. C. Hu, Networks, Vol. 7, No. 4, 1977, pp. 289-296.
    • 36. "Generating Binary Trees Lexicographically," F. Ruskey and T. C. Hu, SIAM Journal on Computing, Vol. 6, No. 4, 1977, pp. 745-758.
    • 37. "Error Bounds and the Applicability of the Greedy Solution to the Coin-Changing Problem," B. N. Tien and T. C. Hu, Operations Research, Vol. 25, No. 3, 1977, pp. 404-418.
    • 38. "Binary Trees Optimum under Various Criteria," T. C. Hu, D. J. Kleitman and J. Tamaki, SIAM Journal on Applied Mathematics, Vol. 37, No. 2, 1979, pp. 246-256.
    • 39. "Assignment of Tasks in a Distributed Processor System with Limited Memory," G. S. Rao, H. S. Stone and T. C. Hu, IEEE Transactions on Computers, Vol. C-28, No. 4, 1979, pp. 291-299.
    • 40. "Circular Cuts in a Network," T. C. Hu and F. Ruskey, Mathematics of Operations Research, Vol. 5, No. 3, 1980, pp. 422-434.
    • 41. "Some Theorems about Matrix Multiplication," T. C. Hu and M. T. Shing, in Proceedings of the 21st Annual Symposium on the Foundations of Computer Science, 1980, pp. 28-36.
    • 42. "An O(n) Algorithm to Find a Near Optimum Partition of a Convex Polygon," T. C. Hu and M. T. Shing, Journal of Algorithms, Vol. 2, No. 2, 1981, pp. 122-138.
    • 43. "An Optimum Algorithm for Matrix Chain Product, Part I," T. C. Hu and M. T. Shing, SIAM Journal on Computing, Vol. 11, No. 2, 1982, pp. 362-373.
    • 44. "An Optimum Algorithm for Matrix Chain Product, Part II," T. C. Hu and M. T. Shing, SIAM Journal on Computing, Vol. 13, No. 2, 1984, pp. 228-251.
    • 45. "Beauty Contests, College Admissions, and Bargaining," T. C. Hu, Journal of Recreational Mathematics, Vol. 14, No. 4, 1981-82, pp. 252-260.
    • 46. "Multi-Terminal Flows in Outerplanar Networks," by T. C. Hu and M. T. Shing, Stanford Operations Research Dept. Report SOL-81-19. Journal of Algorithms, Vol. 4, No. 3, 1983, pp. 241-261.
    • 47. "Optimum Reduction of Programmable Logic Array," T. C. Hu and Y. S. Kuo, Proceedings of the 20th Design Automation Conference, 1983, pp. 553-558.
    • 48. "Triangulation (Tilings) and Certain Block Triangular Matrices," G. B. Dantzig, A. J. Hoffman and T. C. Hu, Mathematical Programming, Vol. 31, No. 1, 1985, pp. 1-14.
    • 49. "A Decomposition Algorithm for Circuit Routing," T. C. Hu and M. T. Shing, in VLSI Circuit Layout, edited by T. C. Hu, and E. S. Kuh, IEEE Press, 1985, pp. 144-152.
    • 50. "The Alpha Beta Routing," T. C. Hu and M. T. Shing, in VLSI Circuit Layout, edited by T. C. Hu, and E. S. Kuh, IEEE Press, 1985, pp. 139-143.
    • 51. "Multi-terminal Flows in a Hypergraph," T. C. Hu and K. Moerder, in VLSI Circuit Layout, edited by T. C. Hu, and E. S. Kuh, IEEE Press, 1985, pp. 81-86.
    • 52. "Effective Algorithms for Optimal PLA Folding," Y. S. Kuo and T. C. Hu. Proceedings of the Second International Symposium on VLSI Technology Systems and Applications, 1985, pp. 199-203.
    • 53. "A Heuristic Algorithm for PLA Block Folding," by Y. S. Kuo, C. Chen and T. C. Hu. Proceedings of the 22nd Design Automation Conference, 1985, pp. 744-747.
    • 54. "A Decomposition Algorithm for Circuit Routing," by T. C. Hu and M. T. Shing. Mathematical Programming Study, No. 24, 1985, pp. 87-103.
    • 55. "A Decomposition Algorithm for Multi-terminal Network Flows," M. T. Shing and T. C. Hu, Discrete Applied Mathematics, Vol. 13, No. 2,3, 1986, pp. 165-181.
    • 56. "Some Optimum Algorithms for Scheduling Problems with Changeover Costs," by T. C. Hu, Y. S. Kuo and F. Ruskey, Operations Research, Vol. 35, No. 1, 1987, pp. 94-99.
    • 57. "Graph Folding and Programmable Logic Array," T. C. Hu and Y. S. Kuo, Networks, Vol. 17, No. 1, 1987, pp. 19-37.
    • 58. "Binary Search on a Tape," T. C. Hu and M. L. Wachs, SIAM Journal on Computing, Vol. 16, No. 3, 1987, pp.537-590.
    • 59. "An Effective Algorithm for Optimal PLA Column Folding", Y. S. Kuo and T. C. Hu, Integration, the VLSI Journal, Vol. 5, No. 3-4, 1987, pp. 217-230.
    • 60. "Anatomy of On-Line Bin Packing," T. C. Hu and A. B. Kahng, submitted to SIAM Journal on Discrete Mathematics.
    • 61. "Optimization of Globally Convex Functions," T. C. Hu, V. Klee and D. Larman, SIAM Journal on Control and Optimization, Vol. 27, No. 5, 1989, pp. 1026-1047.
    • 62. "Book Review of Combinatorial Search by Martin Aigner," T. C. Hu, Bulletin of the American Mathematical Society, Vol. 21, No. 2, 1989, pp. 314-316.
    • 63. "Ancestor Tree for Arbitrary Multi-Terminal Cut Functions," C. K. Cheng and T. C. Hu, in Integer Programming and Combinatorial Optimization, edited by R. Kannan and W. R. Pulleyblank, Univ. of Waterloo Press, 1990, pp. 115-127.
    • 64. "Ancestor Tree for Arbitrary Multi-terminal Cut Functions," C. K. Cheng and T. C. Hu, Annals of Operations Research, Vol. 33, 1991, pp. 199-213.
    • 65a. "The Modular Orientation of VLSI Layout," C. K. Cheng, T. C. Hu and S. Z. Yao, Proceedings of the IEEE International Symposium on Circuits and Systems, 1990, pp. 1600-1603.
    • 65b. "The Orientation of Modules Based on Graph Decomposition," C. K. Cheng, S. Z. Yao, and T. C. Hu, IEEE Transactions on Computers, Vol. 40, No. 6, 1991, pp. 774-780.
    • 66. "Every Tree is Graceful," T. C. Hu and A. B. Kahng, in Applied Geometry and Discrete Mathematics: the Victor Klee Festschrift, edited by P. Gritzmann and B. Sturmfels, volume 4 of the DIMACS Series in Discrete Mathematics and Theoretical Computer Science, the American Mathematical Society/ACM, 1991, pp. 355-358.
    • 67. "A Multi-chip Module Substrate Testing Algorithm," S. Z. Yao, N. C. Chou, C. K. Cheng, and T. C. Hu, Proceedings of the Fourth Annual IEEE International ASIC Conference and Exhibit, 1991, pp. P9:4.1-P9:4.4.
    • 68. "Block-Oriented Programmable Design with Switching Network Interconnect," C. W. Yeh, L. T. Liu, C. K. Cheng, and T. C. Hu, Proceedings of the Synthesis and Simulation Meeting and International Interchange, SASIMI, 1992, pp. 406-414.
    • 69a. "An Optimal Probe Testing Algorithm for the Connectivity Verification of MCM Substrates," S. Z. Yao, N. C. Chou, C. K. Cheng, and T. C. Hu, Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, 1992, pp.264-267.
    • 69b. "An Optimal Probe Testing Algorithm for the Connectivity Verification of MCM Substrates," S.Z. Yao, N.C. Chou, C.K. Cheng, and T.C. Hu, IEEE Transaction on Computer-Aided Design, Vol.13, January (1994) pp.110-121.
    • 70a. "A Multi-Probe Approach for MCM Substrate Testing," S. Z. Yao, N. C. Chou, C. K. Cheng, and T. C. Hu, IEEE International Conference on ASIC, p9:4.1-4, Sept. 1991.
    • 70b. "A Multi-Probe Approach for MCM Substrate Testing," S. Z. Yao, N. C. Chou, C. K. Cheng, and T. C. Hu, IEEE Transactions on Computer-Aided Design, Vol.13, 1994, pp.110-121.
    • 71. "Maximum Folding, A Generalization of Maximum Matching," T. C. Hu, Operations Research `91: Extended Abstracts of the 16th Symposium on Operations Research, Physica Verlag, 1992, pp. 176-178.
    • 72. "Folding an Array of Transistors and Contacts," T. C. Hu, K. E. Moerder, and J. D. Morgenthaler, Proceedings of the 1992 IEEE International Symposium on Circuits and Systems, Vol. 6, pp. 2969-2972.
    • 73. "Maximum Concurrent Flows and Minimum Ratio Cuts," C. K. Cheng and T. C. Hu, Algorithmica, Vol. 8, No. 3, 1992, pp. 233-249.
    • 74. "Solution of the Discrete Plateau Problem," T. C. Hu, A. B. Kahng and G. Robins, Proceedings of the National Academy of Sciences, Vol. 89, No. 19, pp. 9235-9236, 1992.
    • 75. "Optimal Robust Path Planning in General Environments," T. C. Hu, A. B. Kahng, and G. Robins, IEEE Trans. on Robotics and Automation, Dec. 1993, Vol. 9, No. 6, pp. 775-784.
    • 76a. "Dynamic Programming and Graph Optimization Problems," T.C. Hu and J.D. Morgenthaler, Proceedings of the Fifth International Workshop of the Bellman Continuum, Honolulu, 1993.
    • 76b. "Dynamic Programming and Graph Optimization Problems," T.C. Hu and J.D. Morgenthaler, Computers, Mathematics and Applications. Vol. 27, No. 9 (1994) pp. 53-58.
    • 77. "A Multi-Probe Approach for MCM Substrate Testing," S.Z Yao, N. C. Chou, C. K. Cheng, and T. C. Hu, IEEE Trans. on Computer-aided Design, Jan. 1994, Vol. 13, No. 1, pp. 110-121.
    • 78. "Block-Oriented Programmable Design with Switching Network Interconnect," C. W. Yeh, L. T. Liu, C. K. Cheng, and T. C. Hu, IEEE Trans. on VLSI, March 1994, Vol. 2, No. 1, pp. 45-53.
    • 79. "Prim-Dijkstra Trade-offs for Improved Performance-Driven Global Routing," C. J. Alpert, T. C. Hu, J. H. Huang and A. B. Kahng, IEEE Trans. on CAD 14(7) (1995), pp. 890-896.
    • 80. "A New Class of Non-Monotone Threshold Accepting Methods," T. C. Hu, A. B. Kahng and C.-W. A. Tasao, ORSA J. Computing, 7(4) (1995) pp. 417-425.
    • 81. "A Replication Cut for Two-Way Partitioning," L.T. Liu, M.T. Kuo, C.K. Cheng, and T.C. Hu, IEEE Trans. on CAD, May 1995, pp. 623-630. (1997 IEEE Circuit and System Society Best Paper Award, among papers published during the last three years.
    • 82. "Optimum Alphabetic Binary Trees," T. C. Hu and J. D. Morgenthaler, Lecture Notes in Computer Science, vol. 1120, pp. 234-243, Springer-Verlag, August 1996.
    • 83. "Physical Design: Mathematical Models and Methods," Proceedings, First International Symposium on Physical Design, April 1997, pp. 207-210.
    • 84. "Optimum Alphabetic Tree for Binary Search," T.C. Hu and P.A. Tucker, Information Processing Letters, 67(1988), pp. 137-140.
    • 85. "Minimum Cuts without Path Packing," P.A. Tucker, T.C. Hu, and M.T. Shing, Tech. Report, CS 99-625, June 1999.
    • 86. "Minimaxima Programming," P.A. Tucker and T.C. Hu, Tech. Report, CS 99-624, June 1999.
    • 87. "Toward Digital Calculus," T.C. Hu, Tech. Report, CS 99-628, June 1999.
    • 88. "Combinatorial Algorithms and Network Algebra," T.C. Hu and M.T. Shing, Dover, April 2002.

    May 7, 2009

    hu@cs.ucsd.edu