Researcher Skip to main content IBM Research Homepage
 Research Home  >> Alan Hoffman 
PUBLICATIONS
HONORS
PATENTS

ALAN HOFFMAN
 
Alan Hoffman
ALAN HOFFMAN
1961 
Biography 

Born May 30, 1924 in New York City. 
Educated at Columbia (AB, 1947, PhD, 1950). 
Served in U. S. Army, 1943-46. 

1950-51 Member, Institute for Advanced Study, Princeton 
1951-56 Mathematician, National Bureau of Standards, Washington 
1956-57 Scientific Liason Officer, Office of Naval Research, London,U.K. 
1957-61 Consultant, Management Consultation Services, General Electric Company, New York 
1961-2002 Research Staff Member, T. J. Watson Research Center, IBM, Yorktown Heights 
2002 - IBM Fellow Emeritus, T. J. Watson Research Center, IBM, Yorktown Heights 

Alan Hoffman
ALAN HOFFMAN
2002 

Adjunct or Visiting Professor at:

Technion, Israel Institute of Technology, 1965 
City University of New York, 1965-1976 
Yale University, 1975-1985 and 1991 
Stanford University, 1980-1991 
Rutgers University, 1990-1996 
Georgia Institute of Technology, 1992-93 

Students:

Fred Buckley, City University of New York, 1978 
Michael Doob, City University of New York, 1969 
Michael Gargano, City University of New York, 1975 
Allan Gewirtz, City University of New York, 1967 
Rafael Hassin, Yale University, 1977 
Leonard Howes, City University of New York, 1970 
Basharat Jamil, City University of New York, 1976 
Sidney Jacobs, City University of New York, 1971 
Deborah Kornblum, City University of New York, 1978 
S. Thomas McCormick, Stanford University, 1983 
Louis Quintas, City University of New York, 1967 
Peter Rolland, City University of New York, 1976 
Howard Samowitz, City University of New York, 1979 
Robert Singleton, Princeton University, 1962 
Lennox Superville, City University of New York, 1978 

Present or past service on editorial boards of:

Linear Algebra and its Applications (founding editor) 
Mathematics of Operations Research 
Discrete Mathematics 
Discrete Applied Mathematics 
Naval Research Logistics Quarterly 
Journal of Combinatorial Theory 
Combinatorica 
SIAM Journal of Discrete Mathematics 
SIAM Journal of Applied Mathematics 
Mathematics of Computation 
International Computing Center Bulletin 

Honors: 

Member, National Academy of Sciences, 1982- 
IBM Fellow, 1978- 
D. Sc. (Hon.) Technion, 1986 
Fellow, American Academy of Arts and Sciences, 1987- 
Fellow, New York Academy of Sciences, 1975- 
Phi Beta Kappa Lecturer, l989-90 
Special issue of Lin. Alg. Appl., l989, for 65th birthday 
von Neumann Prize (Operations Research Society & 
Institute of Management Science), 1992 
Founder's Award, Mathematical Programming Society, 2000 
Fellow, Institute for Operations Research and Management Science, 2002- 
 

Publications of Alan J. Hoffman

1. On the foundations of inversion geometry, Trans. Amer. Math. Soc. 17:218-242 (1951). 

2. A note on cross ratio, Amer. Math. Monthly 58: 613-614 (1951). 

3. Chains in the projective line, Duke Math. Journal 18:827-830 (1951). 

4. Cyclic affine planes, Can. Jour. Math. 4:295-301 (1952). 

5. On approximate solutions of systems of linear inequaliities, J. Research Natl. Bureau Stds. 49:263-265 (1952). 

6. The variation of the spectrum of a normal matrix, Duke Math. Journal 20: 37-40 (1953) (with H. W. Wielandt). 

7. Computational experience in solving linear programs, Jour. Soc. Ind. Appl. Math. 1:17-34 (1953) (with M. Mannos, D. Sokolowsky And N. Wiegmann). 

8. On a combinatorial theorem, Natl. Bureau Stds. Report 2377 (1953). 

9. On an inequality of Hardy, Littlewood and Polya, Natl. Bureau Stds. Report 2977 (1953). 

10. Cycling in the simplex algorithm, Natl. Bureau Stds. Re- port 2974 (1953). 

11. A characterization of normal matrices, J. Research Natl. Bureau Stds. 52: 17-19 (1954) (with O. Taussky). 

12. On a theorem of Ostrowski and Taussky, Archiv der Mathematik 5: 123-127 (1954) (with R. Bellman). 

13. Lower bounds for the rank and location of the eigenvalues of a matrix, Contributions to the Solution of Systems of Linear equations and the Determination of Eigenvalues, Appl. Math. Series No. 39: 117-130, Washington (1954) (with K. Fan). 

14. On the solution of the caterer problem, Nav. Res. Logist. Quarterly 1:223-229 (1954) (with J. Gaddum And D. Sokolowsky). 

15. Smooth patterns of production, Management Sci. 1:86-91 (1954) (with W. Jacobs). 

16. A remark on the smoothing problem, Managemnt Sci. 1:92-95 (1954) (with H. Antosiewicz). 

17. Some metric inequalities in the space of matrices, Proc. Amer. Math. Soc. 6:111-116 9 (1955) (with K. Fan). 

18. How to solve a linear programming problem, Proc. Second Linear Programming Symposium, 397-424, Washington (1955). 

19. SEAC determines low bidders, Research Reviews, 11-12 (april, 1955). 

20. Linear programming, Research Reviews, 23-27 (august, 1955) (with G. Voegeli). 

21. Linear programming, Applied Mechanics Review 9:185-187 (1956). 

22. The number of absolute points of a correlation, Pac. Jour. Math. 6: 83-96 (1956) (with M. Newman, E. Straus And O. Taussky). 

23. On systems of distinct representatives and linear programming, Amer. Math. Monthly 63:455-460(1956) (with H. Kuhn). 

24. Integral boundary points of convex polyhedra, Annals of Mathematics Study 38: 223-241, Princeton (1956) (with J.Kruskal). 

25. Dilworth's theorem on partially ordered sets, Annals Of Mathematics Study 38:207-214, Princeton (1956) (with G. Dantzig). 

26. On systems of distinct representatives, Annals Of Mathematics Study 38:199-202, Princeton (1956) (with H. Kuhn). 

27. Generalization of a theorem Of Konig, Jour. Wash. Acad. Sciences 46: 211-212 (1956). 

28. Systems of inequalities involving convex functions, Proc. Amer. Math. Soc. 8:617-622 (1957) (with K. Fan And I. Glicksberg). 

29. Geometry, Chapter 8, 97-102, Handbook Of Physics, McGraw-hill (1958) 

30. Linear programming, McGraw-Hill Encyclopedia of Science and Technology 7, 522-523 (1960). 

31. Some recent applications of the theory of linear inequalities to extremal combinatorial analysis, Proc. Symp. in Applied Mathematics, Amer. Math. Soc., 113-127 (1960). 

32. On the uniqueness of the triangular association scheme, Annals of Mathematical Statistics 31: 492-497 (1960). 

33. On the exceptional case in a characterization of the arcs of a complete graph, IBM J. Res. and Dev. 4:487-496 (1960). 

34. On Moore Graphs with diameters 2 and 3, IBM J. Res. and Dev. 4: 497-404 (1960) (with R. Singleton). 

35. Extreme varieties, concave functions and the fixed charge problem, Communications in Pure and Applied Mathematics 14:355-369 (1961) (with W. Hirsch). 

36. Block design games, Canadian Journal of Mathematics 13: 110-128 (196 (with M. Richardson). 

37. On unimodular matrices, Pacific Journal of Mathematics 12:1321-1327 (1962) (with I. Heller). 

38. Finding optimal combinations, Science and Technology, 26-33 (July, 1962) (with R. Gomory) 

39. On the polynomial of a graph, American Mathematical Monthly 70 (30-3 (1963). 

40. On the convergency of an integer-programming process, Naval Research Logistics Quarterly 10:121-123 (1963) (with R. Gomory). 

41. On simple linear programming problems, Proc. Symposia in Pure Mathematics VII, 317-327, Amer. Math. Soc. (1963). 

42. Dynamic programming, 5th IBM Medical Symposium, Endicott (1963). 

43. On the duals of symmetric partially balanced incomplete block designs, Annals of Mathematical Statistics 34:528-531 (1963). 

44. On symmetric bimatrix games, IBM Research Report RC 959 (1963) (with J. Griesmer And A. Robinson). 

45. Shortest path, assignment and transportation problems, Naval Res. Logistics Quarterly 10:375-379 (1963) (with H. Markowitz). 

46. Large linear programs, Proceedings IFIP Congress 1962, 173-176. 

47. A characterization of comparability graphs and of interval graphs, Canadian Journal of Mathematics 15: 539-548 (1964) (with P. Gilmore) 

48. On abstract dual linear programs, Naval Research Logistics Quarterly 10:369-373 (1964). 

49. Linear inequalities and analysis, American Mathematical Monthly 71:416-418 (1964) (with M. McAndrew). 

50. Some properties of the rank and invariant factors of matrices, Canadian Mathematical Bulletin 7:85-96 (1964) (with R. Gomory and N. Hsu). 

51. The line graph of the complete bipartite graph, Annals of Mathematical Statistics 35:883-885 (1964). 

52. Some properties of graphs with multiple edges, Canadian Journal of Mathematics 17:166-177 (1965) (with D. Fulkerson and M. McAndrew) 

53. The polynomial of a directed graph, Proc. Amer. Math. Soc. 16: 303-309 (1965) (with M. McAndrew). 

54. On the line graph of a projective plane, Proc. Amer. Math. Soc. 16: 297-392 (1965). 

55. On the line graph of a finite affine plane, Canadian Journal of Mathematics 17:687-694 (with D. Ray- Chaudhuri). 

56. On the line graph of a symmetric balanced incomplete block design, Transactions Amer. Math. Soc. 116:238-252 (1965) (with D. Ray-Chaudhuri). 

57. The nonsingularity of real matrices, Mathematics of Computation XIX, No. 89:56-61 (1965). 

58. On the nonsingularity of real partitioned matrices, International Journal of Computation and Applied Mathematics 4:7-17 (1965). 

59. On the nonsingularity of complex matrices, Pacific Journal of Mathematics 17:211-214 (1966) (with P. Camion). 

60. On nonterminating stochastic games, Management Science 12:359-370 (1966) (with R. Karp). 

61. Ranks of matrices and families of cones, Transactions New York Academy of Science 29: 375-377 (1967). 

62. Three observations on nonnegative matrices, Journal of Research, National Bureau of Standards 71b:39-41 (1967). 

63. The eigenvalues of the adjacency matrix of a graph, Proc. Symposium on Combinatorial Mathematics,578-584, Univ. North Carolina (1967). 

64. Some recent results on spectral properties of graphs, Beitrage zur Graphentheorie (Proceedings of an International Colloquium), 75-80, B. G. Teubner, Leipzig (1968). 

65. Estimation of eigenvalues of a matrix and the theory of linear inequalities, Proc. AMS Lectures In Applied Mathematics, II,part 1, Mathematicsof The Decision Sciences, 295-300 (1968). 

66. Bounds for the rank and eigenvalues of a matrix, Proc. IFIP Congress 1968, 111-113. 

67. A special class of doubly stochastic matrices, Aequationes Mathematicae 2:319-326 (1969). 

68. The change in the least eigenvalue of the adjacency ma- trix of a graph under imbedding, Siam Journal of Appl. Math. 17:664-671 (1969). 

69. On the covering of polyhedra by polyhedra, Proc. Amer. Math. Soc. 23:123-126 (1969). 

70. On unions and intersections of cones, Recent Progress in Combinatorics, 103-109, Academic Press, New York (1969). 

71. Two remarks on copositive matrices, Linear Algebra Appls. 2:387-392 (1969) (with E. Haynsworth). 

72. Generalizations of Gersgorin's theorem, Lectures given at Univ. California, Santa Barbara (1969). 

73. When is a team "mathematically" eliminated?, Proc. Princeton Symposium On Math. Programming, 1966, 391-401, Princeton (1970) (with T. Rivlin). 

74. On the variation of coordinates in subspaces, Annali Di. Mat. Ser. IV Vol. LXXXVI:53-59 (1970). 

75. Patterns of dependence in generalizations of Gersgorin's theorem, Siam J. on Numerical Analysis 7:571-574 (1970) (with R. Varga). 

76. -1-2?, Combinatorial Structures and Their Applications, 173-176, Gordon And Breach, New York (1970). 

77. On eigenvalues and colorings of graphs, Graph Theory and its Applications, 79-91, Academic Press, New York (1970). 

78. On eigenvalues and colorings of graphs II, Proc. Inter- national Conference for Combinatorial Mathematics, Annals Of The New York Academy of Sciences. 175, 238-242 (1970) (with L. Howes). 

79. Combinatorial aspects of Gersgorin's theorem, Recent Trends in Graph Theory, 173-179, Springer-verlag, New York (1970). 

80. On vertices near a given vertex of a graph, Studies in Pure Mathematics, 131-136, Academic Press, New York (1971). 

81. Eigenvalues and edge partitionings of graphs, Linear Algebra Appls. 5:137-146 (1972). 

82. On finding all shortest distances in a directed network, IBM J. Res. And Dev. 16:412-414 (1972) (with S. 
Winograd). 

83. On limit points of spectral radii of nonnegative symmetric integral matrices, Graph Theory and its Applications, 165-172, Springer Verlag (1972). 

84. Some applications of graph theory, Proceeding Third S.E. Conference on Combinatorics and Computing, 9-14 (1972). 

85. Sparse matrices, Proc. Second Manitoba Conference on Numerical Mathematics (1972). 

86. On spectrally bounded graphs, A Survey of Combinatorial Theory, 277-283, North-Holland (1973). 

87. Complexity bounds for regular finite difference and finite element grids, SIAM Journal on Numerical Analysis 10:364-369 (1973) (with M. Martin And D. Rose). 

88. On copositive matrices with -1,0,1 entries, J. Combinatorial Theory A14: 302-309 (1973) (with F. Pereira). 

89. Lower bounds for the partitioning of graphs, IBM J. Res. and Dev. 17:420-425 (1973) (with W. Donath). 

90. Self-orthogonal latin squares of all orders n = 2,3,6, Bulletin Amer. Math. Soc. 80: 116-118 (1974) (with R. Brayton And D. Coppersmith). 

91. On eigenvalues of symmetric (+1,-1) matrices, Israel Journal Of Mathematics, 17: 69-75 (1974). 

92. A generalization of max flow-min cut, Mathematical Programming 6:352-359 (1974). 

93. On balanced matrices, Mathematical Programming Study 1: 120-132 (1974) (with D. Fulkerson And R. Oppenheim). 

94. Eigenvalues of graphs, Studies in Graph Theory, Part II, 225-245, Mathematical Association Of America (1975). 

95. Linear G-functions, Linear and Multilinear Algebra 3: 45-52 (1975) 

96. On the spectral radii of topologically equivalent graphs, Recent Advances in Graph Theory, 273-282, Czechoslovak Academy Of Sciences (1975). 

97. Applications of Ramsey style theorems to eigenvalues of graphs, Combinatorics, 245-260, D. Reidel Publishing Company, Dordrecht (1975). 

98. Spectral functions of graphs, Proceedings of International Congress of Mathematics 1974, Vol.2, 461-464, Canadian Mathematical Congress (1975). 

99. On convex cones In C , Bulletin of the Institute of Mathematics, Academia Sinica 3:1-6 (1975). 

100. On spectrally bounded signed graphs, Proc. 21st Conference of Army Mathematicians, 1-6, El Paso (1975). 

101. Self-orthogonal latin squares, Colloquio Internationale sulle Teorie Combinatorie, Tomo II, 509-517, Accademia Nazionale Dei Lincei (1976) (with R. Brayton And D. Coppersmith). 

102. Total unimodularity and combinatorial theorems, Linear Algebra Appls. 13: 103-108 (1976). 

103. On graphs whose least eigenvalue exceeds -1 - 2, Linear Algebra Appls. 16:153-166 (1977). 

104. On The line graph of the complete tripartite graph, Linear and Multilinear Algebra:10-25 (1977) (with B. Jamil). 

105. A theorem on inverses of convex sets of real matrices, with application to the worst-case DC problem, IEEE Transactions on Circuits And Systems CAS-24: 409-415 (1977) (with R. Brayton and T. Scott). 

106. On signed graphs and grammians, Geometrie Dedicata 
6:455-470 (1977) 

107. On partitions of a partially ordered set, J. Combinatorial Theory B 23: 3-13 (1977) (with D. Schwartz). 

108. On limit points of the least eigenvalue of a graph, Ars Combinatorica 3:3-14 (1977). 

109. Linear programming and combinatorial problems, Proceedings of a Conference on Discrete Mathematics and its Applications, 65-92, Indiana University (1976). 

110. Nearest -matrices of given rank and the Ramsey problem for eigenvalues of bipartite -graphs, Colloques Internationaux C.N.R.S. 260, Problemes Combinatorie et Theorie des Graphes, 237-240 (1977) (with P. Joffe) 

111. Multicoloration dans les hypergraphes unimodulaires et matrices dont les coefficients sont des ensembles, Colloques Internationaux C.N.R.S.260, Problemes Combinatoire et Theorie des Graphes, 27-30 (1977) (with C. Berge). 

112. On the distance matrix of a graph, Journal of Graph Theory 1:85-88 (1977) (with R. Graham And H. Hosoya). 

113. Local unimodularity in the matching polytope, Annals of Discrete Mathematics 2:201-209 (1978) (with R. Oppenheim). 

114. On lattice polyhedra, Proceedings 5th Hungarian Colloquium on Combinatorics, 593-598 (1978)(with D.E.Schwartz 

115. Polyhedral Combinatorics, Mathematical Programming Study 8, North-Holland (1978) (M. Balinski, Co- editor). 

116. D. R. Fulkerson's contributions to polyhedral combinatorics, Mathematical Programming Study 8:17-23 (1978). 

117. On Lattice Polyhedra III: Blockers and anti-blockers of lattice clutters, Mathematical Programming Study 8:197-207 (1978). 

118. Helly numbers of some sets In R , IBM Research Report RC7319 (1978) 

119. Some greedy ideas, IBM Research Report RC7279 (1978). 

120. The role of unimodularity in applying linear inequalities to combinatorial theorems, Annals of Discrete Mathematics 4:73-84 (1979). 

121. On the mixed achromatic number and other functions of graphs, Graph Theory and Related Topics, 105-119, Academic Press (1979) (with F. Buckley). 

122. Linear programming and combinatorics, Proc. Symposia in Pure Mathematics 34, 245-253, American Mathematical Society (1979). 

123. Binding constraints and Helly numbers, Annals of the New York Academy of Sciences 319, 284-288 (1979). 

124. Polyhedral aspects of discrete optimization, Annals of Discrete Mathematics 4: 183-190 (1979) (with F. Granot). 

125. Maximum degree in graphs of diameter 2, Networks 10:87-96 (1980) (with P. Erdos And S. Fajtlowicz). 

126. Matroid intersections, Combinatorica 1:43-47 (1981) (with H. Groflin). 

127. Ordered sets and linear programming, Ordered Sets, 619-654, D. Reidel Publishing Company (1981). 

128. On bounds for eigenvalues of real symmetric matrices, Linear Algebra Appls. 40:217-223 (1981) (with E. Barnes). 

129. Lattice polyhedra II: construction and examples, Annals of Discrete Mathematics 15:189-203 (1982) (with H. Groflin). 

130. Two remarks on the Mendelsohn-Dulmage theorem, Annals of Discrete Mathematics 15: 171-177 (1982) (with D. Gale). 

131. Extending Greene's theorem to directed graphs, J. Combinatorial Theory A34:102-107 (1983). 

132. On the relationship between the Hausdorff distance and matrix distance of ellipsoids, Linear Algebra Appls. 52:301-313 (1983) (with J. Goffin). 

133. On greedy algorithms in linear programming, Proc. 4th Japanese Mathematical Programming Symposium, 1-13, Kobe (1983). 

134. Partitioning, spectra and linear programming, Progress in Combinatorial Optimization, 13-26, Academic Press (1984) (with E. Barnes). 

135. A fast algorithm that makes matrices optimally sparse,Progress in Combinatorial Optimization, 185-196, Academic Press (1984) (with S. McCormick). 

136. Aspects of the Traveling Salesman problem, IBM J. Res. and Dev. 28:476-486 (1984) (with M. Held, E. Johnson And P. Wolfe). 

137. On the spectral radius of (0,1) matrices, Linear Algebra Appls. 65: 133-146 (1985) (with R. Brualdi). 

138. Path partitions and packs of acyclic digraphs, Pacific Journal of Mathematics 118:249-259 (1985) (with R. Aharoni And I. Hartman). 

139. Triangulations (tilings) and certain block triangular matrices, Mathematical Programming 31: 1-14 (l985) (with G. Dantzig And T. Hu). 

140. On transportation problems with upper bounds on leading rectangles, SIAM Journal on Algebraic and Discrete Methods 6:487-496 (1985) (with E. Barnes). 

141. Totally balanced and greedy matrices, SIAM Journal Algebraic And Discrete Methods:721-730 (l985) (with A. Kolen And M. Sakarovitch). 

142. Line sum symmetric scaling of square nonnegative matrices, Mathematical Programming Study 25:124-141 (l985) (with B. Eaves, U. Rothblum and H. Schneider). 

143. Minimizing a unimodal function of two integer variables, Mathematical Programming Study 25:76-87 (1985) (with P. Wolfe). 

144. History of Traveling Salesman problem, The Traveling Salesman, 1-15, John Wiley (1985) (with P. Wolfe). 

145. On a conjecture of Kojima and Saigal, Linear Algebra Appls. 71: 159-160 (1985) 

146. On greedy algorithms that succeed, Surveys in Combinatorics, 97-112, Cambridge University Press 
(1985). 

147. On the cone of nonnegative circuits, Discrete and Computational Geometry 1:229-239 (1986) (with C. Lee). 

148. A generalization of the Eckart-Young-Mirsky matrix approximation theorem, Linear Algebra Appls. 88/89:317-327 (1987) (with G. Golub And G. Stewart). 

149. Greedy packing and series-parallel Graphs, J. Combinatorial Theory A47:6-15 (1988) (with A. Tucker). 

150. On greedy algorithms for series parallel graphs, Mathematical Programming 40:197-204 (1988) 

151. Linear programming with spheres and hemispheres of objective vectors, Mathematical Programming 51:1-16 (1991) (with B.C. Eaves and H. Hu). 

152. Linear Programming at the National Bureau of Standards, in History of Mathematical Programming, a collection of personal reminiscences, edited by J.K. Lenstra, A. Rinooy-Kan and A. Schrijver, Elsevier Science Publishers, Amsterdam, l991, 62-64 

153. Optimal partitions having disjoint conic and convex hulls, Mathematical Programming 54:69-86 (1992) (with E. R. Barnes and U. Rothblum) 

154. On simple combinatorial optimization problems, Discrete Mathematics 106/107 (1992), 285-289 

155. Monge and feasibility sequences in general flow problems, Discrete Applied Mathematics 44:21-38 (1993) (with Ilan Adler and Ron Shamir). 

156. Festschrift in honor of Philip Wolfe, Mathematical Programming B, vol. 62 (1993), co-editor with R.W. Cottle and D. Goldfarb 

157. Series parallel composition of greedy linear programming problems, Mathematical Programming B 62:1-14 (1993) (with W.W. Bein and P. Brucker). 

158. Staircase transportation problems with superadditive rewards and cumulative capacities, Mathematical Programming B 62:199-214 (1993) (with A.F. Veinott, Jr.) 

159. A proof of the convexity of the range of a nonatomic vector measure using linear inequalities, Linear Algebra Appls.:199 373-380 (1994)(with U. Rothblum) 

160. Bounds for the spectrum of normal matrices, Linear Algebra Appls. 201 79-90 (1994) (with E. Barnes) 

161. Special Issue, Mathematical Sciences Department, T. J. Watson Research Center, IBM Journal of R&D vol.38, number 3 (1994), guest editor 

162. A nonlinear allocation problem, IBM Journal of R&D 38 301-306 (1994) (with E.V. Denardo, T. Mackenzie and W.R. Pulleyblank). 

163. Approximations to Solutions to Systems of Linear Inequalities, SIAM J. Matrix Anal. Appl. Vol 16, 688-696 (1995), (with O. Guler and U. G. Rothblum). 

164. A note on almost regular matrices, Linear Algebra and its Applications 226-228 (1995). 105-108,(with M. Hofmeister and P. Wolfe). 

165. Special Issue honoring J.J. Seidel, Linear Algebra and its Applications 226-228 (1995), co-editor with A. Blokhuis and W. Haemers.

166. A characterization of nonnegative box greedy matrices, Siam Journal of Discrete Mathematics 9:1-6 (1996),(with U. Faigle and W. Kern). 

167. Restrictions and preassignments in preemptive open shop scheduling, Discrete Applied Mathematics 68: 169-188, (1996) (with D. Dewerra, N.V.R. Mahadev and U.N. Peled). 

168. On the existence of sequences and matrices with prescribed partial sums of elements, Linear Algebra and its Applications 265 (1997), 71-92 (with D. Hershkowitz and H. Schneider).

169. Inequalities of Rayleigh quotients and Bounds on the spectral radius of nonnegative symmetric matrices, Linear Algebra and Its Applications 263:201-220 (1997) (with D. Coppersmith and U.G. Rothblum).

170. Variations on a theorem of Ryser, Linear Algebra and its Applications 260: 215-222 (1997), (with D. Cao, V. Chvatal and A. Vince).

171. On computing Ax and pi¬T A, when A is sparse, Annals of Numerical Mathematics 4: 359-368 (1996), (with W. Pulleyblank and J. Tomlin). 

172. On a measure of dissimilarity between positive definite matrices, Annals of Numerical Mathematics 6: 351-358 (1996), (with C. Micchelli). 

173. What Olga did for me. Linear Algebra and its Applications 280:13 (1998). 

174. Special issue on VLSI, Discrete Applied Mathematics 90 (1999), co-editor with M. Minoux and A. Vanelli. 

175. The edge versus path incidence matrix of series parallel graphs and greedy packing, Discrete Applied Mathematics 113:275-284 (2001),
(with B. Schieber)

176. Gersgorin variations I: On a theme of Pupkov and Solov'ev, Linear Algebra and its Applications 304: 173-177 (2000). 

177. Polyhedral combinatorics and totally ordered abelian groups, to appear in Math Programming, Series A. 

178. On a problem of Zaks, Journal of Combinatorial Theory, Series A 93: 371-377 (2001). 

179. On greedy algorithms, partially ordered sets and submodular functions, IBM J. Res. Dev. 47, 25-30 (2003) (with B. L. Dieterich) 

180. New upper bounds for maximum-entropy sampling, mODa 6-Advances in Model-oriented Design and Analysis, 143-153, Physica-Verlag,
Heidelberg(2001), ( with J. Lee and J. Williams).

181. On the submodular matrix representation of a digraph , Theor. Comput. Sci. 287, 563-570 (2002) (with A. Gaillard, H. Groeflin, and W. R. Pulleyblank).  

182. On a game in directed graphs, Information Processing Letters 83, 13-16 (2002) (with K. Jenkins and T. Roughgarden) 

183. Selected Papers of Alan Hoffman, with commentary and autobiographical notes, (edited by Charles Micchelli), World Scientific Publishing Company, Singapore (2003). 

184. Gersgorin Variations II; On Themes of Fan and Gudkov, to appear in Linear Algebra and its Applications. 

185. Remarks on the perfect graph and pluperfect graph theorems, to appear in Discrete Mathematics. 

186. On the singularity of matrices, to appear in Linear Algebra and its Applications (with Don Coppersmith). 

Patents

1. Processing System and Method for Performing Sparse Matrix Multiplication by Reordering Vector Blocks, U.S. Patent 5,905,666, May 18, 1999, with W.Pulleylank and J. Tomlin. 

2. Algorithm for Partitioning of Graphs & Computer Logic Ba, Disclosure YO8710365, with W.E. Donath. 

3. Efficient Pseudo-Matrix Multiplication; Finding All Short, Disclosure YO8710608, with S. Winograd. 

4. Spatial Placement Algorithm for a Scheduling Problem, Disclosure YO8720244, with E. Johnson. 

5. . Making Matrices Sparsest, Disclosure YO8820316, with T.S. McCormick. 

6. Algorithm for Minimizing a Convex Function of Two, Disclosure YO8820385, with P.S. Wolfe. 

7. A Procedure for Partitioning the Nodes of a Graph, Disclosure YO8840645, with E.R. Barnes, A. Vannelli, and P.S. Wolfe. 


 Privacy | Legal | Contact | IBM Home | Research Home | Project List | Research SitesPage Contact