Nimrod Megiddo’s bio page

CONTENTS

• Degrees
• Institutions where I held visiting positions
• Awards
• Memberships in Editorial Boards
• Grants and Research Contracts
• Publications: Journal Articles,   Chapters in books and papers in proceedings,   Technical Reports
• Patents

---

Back to home page

Degrees

(all from The Hebrew University of Jerusalem, Israel):

• 1968 – B.Sc., Mathematics, Physics and Complementary Studies
• 1969 – M.Sc., Mathematics
• 1972 – Ph.D., Mathematics

Permanent positions:

• Tel Aviv University, School of Mathematical Sciences, 1972 – 1998.
• IBM Corp., Almaden Research Center, Foundations: Principles and Methodologies, 1984 – to date.

Institutions where I held visiting positions:

• Tokyo Institute of Technology, 1975.
• University of Illinois at Urbana-Champaign, College of Commerce and Business Administration, 1977/78.
• Northwestern University, Kellogg Graduate School of Management, 1978/79, 1981.
• National Research Institute for Mathematical Sciences, C.S.I.R., South Africa, 1981.
• Carnegie-Mellon University, Graduate School of Industrial Administration, 1982/83.
• Stanford University, Computer Science Department, 1983/84.
• Xerox Corp., PARC (Palo Alto Research Center), 1984.
• MSRI (Mathematical Sciences Research Institute), Berkeley, California, 1985/86.

Awards:

• The Joseph Levy Prize, ORSIS – Operations Research Society – Israel, 1986.
• ICS Prize, INFORMS Computer Society, 1992.
• Outstanding Innovation Award, IBM Corp., 1992.
• Frederick W. Lanchester Prize, INFORMS – Institute for Operations Research and the Management Sciences (formerly the Operations Research Society of America), 1992.
• Outstanding Innovation Award, IBM Corp., 1995.
• Pat Goldberg Memorial Best Paper Award, 2003.
• Outstanding Innovation Award, IBM Corp., 2004.
• Pat Goldberg Memorial Best Paper Award, 2005.

Editorial Board Memberships

• Mathematics of Operations Research:
• Editor-in-Chief, 2004 – to date.
• Area Editor for Game Theory (1999-2003) and Machine Learning (1999 – to date).
• Associate Editor, 1983 – 1992.
• Discrete Optimization:

o Editor-in-Chief, 2007 – to date

o Member of the Editorial Board, 2004 – 2007.

• Journal of the ACM: Area Editor for Operations Research, Game Theory, and Economics, 1988 – to date.
• Operations Research Letters: Area Editor for Game Theory, 2002 – to date.
• Algorithmica: Member of the Editorial Board, 1985 – to date.
• Mathematical Programming: Associate Editor, 1986 – to date.
• Discrete Applied Mathematics: Member of the Editorial Board, 1987 – to date.
• Games and Economic Behavior: Member of the Editorial Board, 1988 – to date.
• Journal of Combinatorial Optimization: Member of the Editorial Board, 1995 – to date.
• SIAM Journal on Discrete Mathematics: Member of Editorial Board, 1987 – 1993.

Grants and Research Contracts:

• Studies in Locations, Allocations and Placements, NSF – National Science Foundation, 1982 – 1984.
• Linear Programming and Related Problems in Lower Dimensional Spaces, NSF – National Science Foundation, 1983 – 1985.
• Analysis of Solution Paths in Linear Programming and Extensions, ONR – Office of Naval Research, 1987 – 1990.
• Studies on the Complexity of Linear Programming and Related Topics, ONR – Office of Naval Research, 1991 – 1993.
• Topics in Linear Programming and Related Problems,  ONR – Office of Naval Research, 1994 – 1997.

Books

1. N. Megiddo, Essays in Game Theory in Honor of Michael Maschler (edited), Springer–Verlag, New York, 1994.
2. M. Kojima, N. Megiddo, T. Noma and A. Yoshise, "A unified approach to interior point algorithms for linear complementarity problems," Lecture Notes in Computer Science 538, Springer-Verlag, 1991.
3. N. Megiddo, Progress in Mathematical Programming: Interior-Point and Related Methods (edited), Springer–Verlag, New York, 1988.
4. N. Megiddo, Y. Xu, and B. Zhu, Algorithmic Applications in Management, First International Conference, AAIM 2005, Xian, China, June 22-25, 2005, Proceedings Springer 2005.
5. Books in Hebrew

Journal articles

1. N. Megiddo, "The kernel and the nucleolus of a product of simple games," Israel Journal of Mathematics 9 (1971), No. 9, 210–221.

2. N. Megiddo, "Nucleoluses of compound simple games," SIAM Journal on Applied Mathematics 26 (1974), No. 3, 607–621.

3. N. Megiddo, "Kernels of compound games with simple components," Pacific Journal of Mathematics 50 (1974), No. 2, 531–555.

4. N. Megiddo, "On the nonmonotonicity of the bargaining set, the kernel and the nucleolus of a game," SIAM Journal on Applied Mathematics 27 (1974), No. 2, 355–358.

5. N. Megiddo, "Optimal flows in networks with multiple sources and sinks," Mathematical Programming 7 (1974), No. 3, 97–107.

6. N. Megiddo, "Tensor decomposition of cooperative games," SIAM Journal on Applied Mathematics 29 (1975), No. 3, 388–405.

7. N. Megiddo, "Partial and complete cyclic orders," Bulletin of the American Mathematical Society 82 (1976), No. 2, 274–276.

8. N. Megiddo, "On monotonicity in parametric linear complementarity problems," Mathematical Programming 12 (1977), No. 1, 60–66.

9. N. Megiddo and M. Kojima, "On the existence and uniqueness of solutions in nonlinear complementarity theory," Mathematical Programming 12 (1977), No. 1, 110–130.

10. N. Megiddo, "A monotone linear complementarity problem with feasible solutions but no complementary solutions," Mathematical Programming 12 (1977), No. 1, 131–132.

11. N. Megiddo, "A good algorithm for lexicographically optimal flows in multi-terminal networks," Bulletin of the American Mathematical Society 83 (1977), No. 3, 407–409.

12. N. Megiddo, "Mixtures of order matrices and generalized order matrices," Discrete Mathematics 19 (1977), No. 2, 177–181.

13. Z. Galil and N. Megiddo, "Cyclic ordering is NP-complete," Theoretical Computer Science 5 (1977), No. 2, 179–182.

14. N. Megiddo and A. Tamir, "An O(n log n) algorithm for a class of matching problems," SIAM Journal on Computing 7 (1978), No. 2, 154–157.

15. N. Megiddo, "On the parametric nonlinear complementarity problem," Mathematical Programming Study 7 (1978), ("Complementarity and fixed point problems," M. L. Balinski and R. W. Cottle, eds.), 142–150.

16. N. Megiddo, "Cost allocation for Steiner trees," Networks 8 (1978), No. 1, 1–6.

17. N. Megiddo, "Computational complexity of the game theory approach to cost allocation on a tree," Mathematics of Operations Research 3 (1978) No. 3, 189–196.

18. N. Megiddo, "Edge three-coloring of tournaments," SIAM Review 20 (1978), No. 3, p. 593.

19. Z. Galil and N. Megiddo, "A fast selection algorithm and the problem of optimum distribution of effort," Journal of the Association for Computing Machinery 26 (1979), No. 1, 58–64.

20. N. Megiddo and Z. Galil, "On Fulkerson's conjecture about consistent labeling processes," Mathematics of Operations Research 4 (1979), No. 3, 265–267.

21. N. Megiddo, "Combinatorial optimization with rational objective functions," Mathematics of Operations Research 4 (1979) 414–424.

22. M. I. Kamien and N. Megiddo, "An intergenerational cake eating game," Economics Letters 2 (1979) 5–7.

23. E. Kalai and N. Megiddo, "Path-independent choices," Econometrica 48 (1980), No. 3, 781–784.

24. N. Megiddo, "On repeated games with incomplete information played by non-Bayesian players," International Journal of Game Theory 9 (1980), No. 3, 157–167.

25. N. Megiddo, A. Tamir, E. Zemel and R. Chandrasekaran, "An O(n (log n) ^2) algorithm for the k'th nearest pair in a tree with applications to location problems," SIAM Journal on Computing 10 (1981), No. 2, 328–337.

26. N. Megiddo, "On the complexity of the one-terminal network design problem," Operations Research Letters 1 (1982), No. 3, 105–107.

27. N. Megiddo, "Is binary encoding appropriate for the problem-language relationship?" Theoretical Computer Science 19 (1982) 337–341.

28. N. Megiddo and A. Tamir, "On the complexity of locating linear facilities in the plane," Operations Research Letters 1 (1982), No. 5, 194–197.

29. N. Megiddo, "Towards a genuinely polynomial algorithm for linear programming," SIAM Journal on Computing 12 (1983), No. 2, 347–353.

30. N. Megiddo, E. Zemel and S. L. Hakimi, "The maximum coverage location problem," SIAM Journal on Algebraic and Discrete Methods 4 (1983), No. 2, 253–261.

31. N. Megiddo and A. Tamir, "Finding least-distances lines," SIAM Journal on Algebraic and Discrete Methods 4 (1983), No. 2, 207–211.

32. N. Megiddo, "Linear-time algorithms for linear programming in R^3 and related problems," SIAM Journal on Computing 12 (1983), No. 4, 759–776.

33. N. Megiddo and A. Tamir, "New results on the complexity of p-center problems," SIAM Journal on Computing 12 (1983), No. 4, 751–758.

34. N. Megiddo, "Applying parallel computation algorithms in the design of serial algorithms," Journal of the Association for Computing Machinery 30 (1983), No. 4, 852–865.

35. N. Megiddo, "The weighted Euclidean 1-center problem," Mathematics of Operations Research 8 (1983), No. 4, 498–504.

36. N. Megiddo, "Linear programming in linear time when the dimension is fixed," Journal of the Association for Computing Machinery 31 (1984), No. 1, 114–127.

37. N. Megiddo and K. J. Supowit, "On the complexity of some common geometric location problems," SIAM Journal on Computing 13 (1984), No. 1, 182–196.

38. I. Adler, N. Megiddo and M. J. Todd, "New results on the behavior of simplex algorithms," Bulletin of the American Mathematical Society 11 (1984), No. 2, 378–382.

39. N. Megiddo and T. Ichimori, "A two-resource allocation problem solvable in linear time," Mathematics of Operations Research 10 (1985), No. 1, 7–16.

40. R. Hassin and N. Megiddo, "An optimal algorithm for finding all the steps of a monotone step-function," Journal of Algorithms 6 (1985) 265–274.

41. I. Adler and N. Megiddo, "A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension," Journal of the Association for Computing Machinery 32 (1985) 871–895.

42. N. Megiddo, "Partitioning with two lines in the plane," Journal of Algorithms 6 (1985) 430–433.

43. N. Megiddo, "A note on the generality of the self-dual algorithm with various starting points," Methods of Operations Research 49 (1985) 271–275.

44. J. Y. Halpern, N. Megiddo and A. A. Munshi, "Optimal precision in the presence of uncertainty," Journal of Complexity 1 (1985), No. 2, 170–196.

45. N. Megiddo and E. Zemel, "A randomizing O(n log n) algorithm for the weighted Euclidean 1-center problem," Journal of Algorithms 7 (1986) 358–368..

46. N. Megiddo, "On the expected number of linear complementarity cones intersected by random and semi-random rays," Mathematical Programming 35 (1986), No. 2, 225–235.

47. N. Megiddo, "Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm," Mathematical Programming 35 (1986) 140–172.

48. N. Megiddo, "Dynamic location problems," Annals of Operations Research 6 (1986) 313–319.

49. J. O'Rourke, S. R. Kosaraju and N. Megiddo, "Computing circular separability," Discrete and Computational Geometry 1 (1986) 105–113.

50. N. Megiddo, "A note on degeneracy in linear programming," Mathematical Programming 35 (1986), No. 3, 365–367.

51. N. Megiddo, "Introduction: New approaches to linear programming," Algorithmica 1 (1986) 387–394.

52. N. Megiddo, "Linear programming (1986)," Annual Review of Computer Science 2 (1987) 119–145.

53. N. Megiddo, "On the complexity of polyhedral separability," Discrete and Computational Geometry 3 (1988) 325–327.

54. N. Megiddo and U. Vishkin, "On finding a minimum dominating set in a tournament," Theoretical Computer Science 61 (1988) 307–316.

55. N. Megiddo, S. L. Hakimi, M. R. Garey, D. S. Johnson and C. H. Papadimitriou, "On the complexity of searching a graph," Journal of the Association for Computing Machinery 35 (1988) 18–44.

56. R. Hassin and N. Megiddo, "On orientations and shortest paths," Linear Algebra and Its Applications 114/115 (1989) 589–602.

57. N. Megiddo, "On computable beliefs of rational machines," Games and Economic Behavior 1 (1989) 144–169.

58. N. Megiddo and B. O'Neill, " 'Inscrutable' badges for verifying a mobile missile quota," Defense Analysis 5 (1989) 260–262.

59. N. Megiddo and R. Chandrasekaran, "On the epsilon-perturbation method for avoiding degeneracy," Operations Research Letters 8 (1989) 305–308.

60. N. Megiddo, "Extending NC and RNC algorithms," Algorithmica 4 (1989) 511–517.

61. N. Megiddo and M. Shub, "Boundary behavior of interior point algorithms in linear programming," Mathematics of Operations Research 14 (1989), No. 1, 97–146.

62. N. Megiddo, "On the ball spanned by balls," Discrete and Computational Geometry 4 (1989) 605–610.

63. R. Fagin, J. Y. Halpern and N. Megiddo, "A logic for reasoning about probabilities," Information and Computation 87 (1990) 78–128.

64. N. Megiddo, "On solving the linear programming problem approximately," Contemporarty Mathematics 114 (1990) 35–50.

65. G. S. Lueker, N. Megiddo and V. Ramachandran, "Linear programming with two variables per inequality in poly log time," SIAM Journal on Computing 19 (1990) 1000–1010.

66. N. Megiddo, "On the complexity of some geometric problems in unbounded dimension," Journal of Symbolic Computation 10 (1990) 327–334.

67. R. Hassin and N. Megiddo, "Approximation algorithms for hitting objects by straight lines," Discrete Applied Mathematics 30 (1991) 29–42.

68. M. Kojima and N. Megiddo, "The relation between the path of centers and Smale's regularization of the linear programming problem," Linear Algebra and Its Applications 152 (1991) 135–139.

69. N. Megiddo and C.H. Papadimitriou, "A note on total functions, existence theorems and complexity," Theoretical Computer Science 81 (1991) 317–324.

70. M. Kojima, N. Megiddo and T. Noma, "Homotopy continuation methods for nonlinear complementarity problems," Mathematics of Operations Research 16 (1991) 754–774.

71. R. Hassin and N. Megiddo, "Exact computation of optimal inventory policies over an unbounded horizon," Mathematics of Operations Research 16 (1991) 534–546.

72. M. Kojima, N. Megiddo, T. Noma and A. Yoshise, "A unified approach to interior point algorithms for linear complementarity problems: A summary," Operations Research Letters 10 (1991) 247–254.

73. N. Megiddo, "On finding primal- and dual-optimal bases," ORSA Journal of Computing 3 (1991) 63–65.

74. D. Koller and N. Megiddo, "The complexity of two-person zero-sum games in extensive form," Games and Economic Behavior 4 (1992) 528–552.

75. N. Megiddo, "A note on approximate linear programming," Information Processing Letters 2 (1992) 53.

76. M. Kojima, N. Megiddo and Y. Ye, "An interior point potential reduction algorithm for the linear complementarity problem," Mathematical Programming 54 (1992), No. 3, 267–279.

77. M. Kojima, N. Megiddo and S. Mizuno, "A general framework of continuation methods for complementarity problems," Mathematics of Operations Research 18 (1993) 945–963.

78. M. Kojima, N. Megiddo and S. Mizuno, "Theoretical convergence of large-step primal-dual interior point algorithms for linear programming," Mathematical Programming 59 (1993) 1–22.

79. E. Cohen and N. Megiddo, "Strongly polynomial-time and NC algorithms for detecting cycles in dynamic graphs," Journal of the Association for Computing Machinery 40 (1993) 791–832.

80. N. Megiddo and A. Tamir, "Linear time algorithms for some separable quadratic programming problems," Operations Research Letters 13 (1993) 203–211.

81. D. S. Hochbaum, N. Megiddo, J. Naor, and A. Tamir, "Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality," Mathematical Programming 62 (1993) 69–84.

82. M. Kojima, N. Megiddo and S. Mizuno, "A primal-dual infeasible-interior-point algorithm for linear programming," Mathematical Programming 61 (1993) 263–280.

83. D. Koller and N. Megiddo, "Constructing small sample spaces satisfying given constants," SIAM Journal on Discrete Mathematics 7 (1994) 260–274.

84. N. Alon and N. Megiddo, "Parallel linear programming in fixed dimension almost surely in constant time," Journal of the Association for Computing Machinery 41 (1994), No. 2, 422–434.

85. E. Cohen and N. Megiddo, "Improved algorithms for linear inequalities with two variables per inequality," SIAM Journal on Computing 23 (1994) 1313–1350.

86. E. Cohen and N. Megiddo, "Algorithms and complexity analysis of some flow problems," Algorithmica 11 (1994) 320–340.

87. E. Cohen and N. Megiddo, "New algorithms for generalized network flows," Mathematical Programming 64 (1994) 325–336.

88. D. Koller, N. Megiddo and B. von Stengel, "Efficient computation of equilibria for extensive two-person games," Games and Economic Behavior 14 (1996) 220–246.

89. D. Koller and N. Megiddo, "Finding mixed strategies with small supports in extensive form games," International Journal of Game Theory 25 (1996) 73–92.

90. T. Hegedus and N. Megiddo, "On the geometric separability of boolean functions," Discrete Applied Mathematics 66 (1996) 205–218.

91. M. Ajtai and N. Megiddo, "A deterministic poly(log log n)-time n-processor algorithm for linear programming in fixed dimension," SIAM Journal on Computing 25 (1996) 1171–1195.

92. N. Megiddo, S. Mizuno and T. Tsuchiya, "A linear programming instance with many crossover events," Journal of Complexity 12 (1996) 474–479.

93. M. Kojima, N. Megiddo and S. Mizuno, "A conjugate direction method for approximating the analytic center of a polytope," Journal of Inequalities and Applications 2 (1998) 181–194.

94. N. Megiddo, S. Mizuno, and T. Tsuchiya, "A modified layered-step interior-point algorithm for Linear Programming," Mathematical Programming 82 (1998), No. 3, 339–355.

95. P. Beling and N. Megiddo, "Using fast matrix multiplication to find basic solutions," Theoretical Computer Science 205 (1998) 307–316.

96. T. Feder, N. Megiddo, and S. A. Plotkin, "A sublinear parallel algorithm for stable matching," Theoretical Computer Science 233 (2000) 297–308.

97. M. Ajtai, N. Megiddo and O. Waarts, "Improved algorithms and analysis for secretary problems and generalizations," SIAM Journal on Discrete Mathematics 14 (2001), No. 1, 1–27.

98. N. Megiddo and D. S. Modha, "One up on LRU," ;login: 28 (2003), No. 4, 7–11.

99. N. Megiddo and  D. S. Modha, "Outperforming LRU with an adaptive replacement cache algorithm," Computer 37 (2004), No. 4, 58–65.

100. D. P. de Farias and N. Megiddo, “Combining expert advice in reactive environments,” J. ACM 53 (2006), No. 5, 762-799.

101. V. Markl, P. Haas, M. Kutsch, N. Megiddo, U. Srivastava, and T.M. Tran, “Consistently selectivity estimation via maximum entropy,” VLDB Journal 16 (2007), No. 1, 55-76.

Chapters in Books and Papers in Conference Proceedings

1. Z. Galil and N. Megiddo, "A fast selection algorithm and the problem of optimum distribution of effort," Proceedings of Conference on Theoretical Computer Science, University of Waterloo, Waterloo, Ontario, Canada, 1977.

2. N. Megiddo, "Combinatorial optimization with rational objective functions," Proceedings of the 10th Annual ACM Symposium on Theory of Computing (1978), ACM, New York, 1978, pp. 1–12.

3. N. Megiddo, S. L. Hakimi, M. R. Garey, D. S. Johnson and C. H. Papadimitriou, "The complexity of searching a graph," Proceedings of the 22nd IEEE Symposium on Foundations of Computer Science (1981), IEEE Computer Society Press, Los Angeles, 1981, pp. 376–385.

4. N. Megiddo, "Applying parallel computation algorithms in the design of serial algorithms," Proceedings of the 22nd IEEE Symposium on Foundations of Computer Science (1981), IEEE Computer Society Press, Los Angeles, 1981, pp. 399–408

5. N. Megiddo, "Linear-time algorithms for linear programming in R^3 and related problems," Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science (1982), IEEE Computer Society Press, Los Angeles, 1982, pp. 329–338.

6. I. Adler and N. Megiddo, "A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension," Proceedings of the 16th ACM Symposium on the Theory of Computing (1984), ACM, New York, 1984, pp. 312–323.

7. J. Y. Halpern, N. Megiddo and A. A. Munshi, "Optimal precision in the presence of uncertainty," Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing (1985), ACM, New York, 1985, pp. 346–355.

8. N. Megiddo and A. Wigderson, "On play by means of computing machines," in: Theoretical Aspects of Reasoning about Knowledge, J. Y. Halpern, ed., Morgan Kaufmann Publishers, Inc., Los Altos, California, 1986, pp. 259–274.

9. N. Megiddo, "Linear programming (1986)," Annual Review of Computer Science 2 (1987) pp. 119–145.

10. N. Megiddo, "On the complexity of linear programming," in: Advances in economic theory: Fifth world congress, T. Bewley, ed., Cambridge University Press, Cambridge, 1987, pp. 225–268.

11. N. Megiddo, "Pathways to the optimal set in linear programming," in: Progress in Mathematical Programming: Interior-Point and Related Methods, N. Megiddo, ed., Springer-Verlag, New York, 1988, pp. 131–158; also in: Proceedings of the 7th Mathematical Programming Symposium of Japan, Nagoya, Japan, 1986, pp. 1–35.

12. R. Fagin, J. Y. Halpern and N. Megiddo, "A logic for reasoning about probabilities," Proceedings of the Third IEEE Symposium on Logic in Computer Science, 1988, pp. 277–291.

13. G. S. Lueker, N. Megiddo and V. Ramachandran, "Linear programming with two variables per inequality in poly log time," Proceedings of the 18th Annual ACM Symposium on Theory of Computing (1986), ACM, New York, 1986, pp. 196–205.

14. E. Cohen and N. Megiddo, "Recognizing properties of periodic graphs," in: Applied Geometry and Discrete Mathematics – The Victor Klee Festschrift, P. Gritzmann and B. Sturmfels, Eds., DIMACS Series in Discrete Mathematics and Theoretical Computer Science Vol. 4, American Mathematical Society and ACM, Providence, RI, 1991, pp. 135–146.

15. N. Megiddo, "Linear Programming," Encyclopedia of Microcomputers Vol. 10, Marcel Dekker, Inc., New York, 1992, pp. 205–210.

16. E. Cohen and N. Megiddo, "Strongly polynomial-time and NC algorithms for detecting cycles in dynamic graphs," Proceedings of the 21st Annual ACM Symposium on Theory of Computing (1989), ACM, New York, 1989, pp. 523–534.

17. N. Megiddo, "A general NP-completeness theorem," in: From topology to computation - from Proceedings of the Smale Fest, M. Hersh, J. Marsden, and M. Shub, Eds., Springer-Verlag, New York, 1993, pp. 432–442.

18. E. Cohen and N. Megiddo, "Maximizing concave functions in fixed dimension," in: Complexity in Numerical Optimization, P. M. Pardalos, Ed., World Scientific, Singapore, 1993, pp. 74–87.

19. N. Megiddo, M. Naor, and D. P. Anderson, "The minimum reservation rate problem in digital audio/video systems," in: Proceedings of ISTCS'93 – The Second Israel Symposium on the Theory of Computing and Systems, IEEE Computer Society Press, San Diego, 1993, pp. 43–48.

20. D. Koller and N. Megiddo, "Constructing small sample spaces satisfying given constraints," Proceedings of the 25th Annual ACM Symposium on Theory of Computing (1993), ACM, New York, 1993, pp. 268–277.

21. T. Feder, N. Megiddo, and S. A. Plotkin, "A sublinear parallel algorithm for stable matching," Proceedings of the Fifth Annual ACM/SIAM Symposium on Discrete Algorithms (1994), pp. 632–637.

22. N. Alon and N. Megiddo, "Parallel linear programming in fixed dimension almost surely in constant time," Proceedings of the 31st IEEE Symposium on Foundations of Computer Science (1990), IEEE Computer Society Press, Los Angeles, 1990, pp. 574–582.

23. N. Megiddo, "On probabilistic machines, bounded rationality, and average-case complexity," in: Essays in Game Theory in Honor of Michael Maschler, Springer-Verlag, New York, 1994, pp. 123–128.

24. E. Cohen and N. Megiddo, "Improved algorithms for linear inequalities with two variables per inequality," Proceedings of the 23rd Annual ACM Symposium on Theory of Computing (1991), ACM, New York, 1991, pp. 145–154.

25. E. Cohen and N. Megiddo, "Algorithms and and complexity analysis of some flow problems," Proceedings of the Second Annual ACM/SIAM Symposium on Discrete Algorithms (1991), pp. 120–130.

26. M. Kojima, N. Megiddo, S. Mizuno and S. Shindoh, "Decomposition in Interior-Point Methods," in: Proceedings Optimization – Modeling and Algorithms, The Institute of Statistical Mathematics, Minato-ku, Tokyo, March 1994..

27. E. Cohen and N. Megiddo, "New algorithms for generalized network flows," Proceedings of ISTCS'92 – The 1992 Israel Symposium on the Theory of Computing and Systems, Lecture Notes in Computer Science, Vol. 601, D. Dolev, Z. Galil, and M. Rodeh, Eds., Springer-Verlag, Berlin, 1992, pp. 103–114.

28. D. Koller, N. Megiddo and B. von Stengel, "Fast algorithms for finding randomized strategies in game trees," Proceedings of 26th Annual ACM Symposium on Theory of Computing (1994), ACM, New York, 1994, pp. 750–759.

29. M. Ajtai and N. Megiddo, "A deterministic poly(log log n)-time n-processor algorithm for linear programming in fixed dimension," Proceedings of the 24th Annual ACM Symposium on Theory of Computing (1992), ACM, New York, 1992, pp. 327–337.

30. M. Ajtai, N. Megiddo and O. Waarts, "Improved algorithms and analysis for secretary problems and generalizations," Proceedings of the 36th IEEE Symposium on Foundations of Computer Science (1995) , IEEE Computer Society Press, Los Angeles, 1995, pp. 473–482.

31. Q. Huang, B. Dom, N. Megiddo and W. Niblack, "Segmenting and representing background in color images," in: Proceedings of the 13th International Conference on Pattern Recognition (ICPR'96, Technical University of Vienna, Austria, August 25–30, 1996), International Association for Pattern Recognition (IAPR), 1996.

32. Q. Huang and N. Megiddo, "Color image background segmentation and representation," in: Proceedings of the 1996 IEEE International Conference on Image Processing (ICIP'96, September 16–19, 1996, Lausanne, Switzerland), IEEE Signal Processing Society, 1996.

33. M. Dyer and N. Megiddo, "Linear programming in low dimensions," in: CRC Handbook of Discrete and Computational Geometry, E. Goodman and J. O'Rourke, Eds., CRC Press, Inc., Boca Raton, New York, 1997, pp. 699–710.

34. C.-T. Ho, R. Agrawal, N. Megiddo and R. Srikant, "Range queries in OLAP data cubes," Proceedings of the 1997 ACM–SIGMOD International Conference on Management of Data, Tucson, Arizona, May 1997, pp. 73–88.

35. N. Megiddo and V. Sarkar "Optimal weighted loop fusion for parallel programs," Proceedings of the Ninth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA'97), Newport, Rhode Island, June 22–25, 1997, pp. 282–291

36. S. Sarawagi, R. Agrawal, and N. Megiddo, "Discovery-driven exploration of OLAP data cubes," Advances in Database Technology – EDBT'98, 6th International Conference on Extending Database Technology, Valencia, Spain, March 23–27, 1998, Proceedings. Lecture Notes in Computer Science 1377 Springer 1998, pp. 168–182.

37. N. Megiddo and R. Srikant, "Discovering predictive association rules," Proceedings of the Fourth International Conference on Knowledge Discovery and Data Mining (KDD–98), August 27–31, 1998,  New York, pp. 274–278.

38. J. Shepherd, X. Zhu and N. Megiddo, "A fast indexing method for multidimensional nearest neighbor search," Proc. of the IS&T/SPIE Conf. on Storage and Retrieval of image and video databases VII, pp. 350–355, 1999.

39. T. Syeda-Mahmood, P. Raghavan and N. Megiddo, "Interval hash tree: An efficient index structure for searching object queries in large image databases," IEEE Workshop on Content-Based Access of Image and Video Libraries  (CBAIVL–2000; in conjunction with IEEE CVPR–2000), Hilton Head, South Carolina, June 12, 2000.

40. V. Sarkar and N. Megiddo, "An analytical model for loop tiling and its solution," ISPASS–2000, IEEE International Symposium on Performance Analysis of Systems and Software, April 24–25, 2000, Austin, Texas.

41. J. Langford, M. Seeger and N. Megiddo, "An Improved Predictive Accuracy Bound for Averaging Classifiers," Proc. of the 18th International Conference on Machine Learning (ICML–2001) June 28 – July 1, 2001, Williams College, Morgan-Kaufmann Publishers, San Francisco, 2001, pp. 290–297.

42. F. Naumann, C. T. Ho, X. Tian, L. Haas and N. Megiddo, "Attribute Classification Using Feature Analysis," 18th IEEE International Conference on Data Engineering (ICDE), San Jose, California, February 26 – March 1, 2002.

43. J. Rao, C. Zhang, G. M. Lohman and N. Megiddo, "Automating Physical Database Design in a Parallel Database," ACM SIGMOD Conference, Madison, Wisconsin, June 3–6, 2002, pp. 558–569.

44. N. Megiddo and D. S. Modha, "ARC: A Self-Tuning, Low Overhead Replacement Cache," Proc. of the 2nd USENIX Conference on File and Storage Technologies (FAST–2003) March 31 – April 2, 2003, San Francisco, pp. 115–130.

45. D. de Farias and N. Megiddo, "How to Combine Expert (or Novice) Advice  when Actions Impact the Environment," Proceedings of Neural Information Processing Systems (NIPS 2003).

46. M. Dyer, N. Megiddo and E. Welzl, "Linear Programming," in: CRC Handbook of Discrete and Computational Geometry, Second Edition, E. Goodman and J. O'Rourke, Eds., CRC Press, Inc., Boca Raton, New York, 2004, pp. 999–1014.

47. D. de Farias and N. Megiddo, "Exploration-Exploitation Tradeoffs for Experts Algorithms in Reactive Environments," Proceedings of Neural Information Processing Systems (NIPS 2004).

48. V. Markl, N. Megiddo, M. Kutsch, T. M. Tran, P. Hass, and U. Srinivasta, "Consistently Estimating the Selectivity of Conjuncts of Predicates," Proceedings of VLDB 2005, pp. 373-384.

49. U. Srivastava, P. Hass, V. Markl, N. Megiddo, M. Kutsch, and T. M. Tran, "ISOMER: Consistent Histogram Construction Using Query Feedback," 22nd IEEE International Conference on Data Engineering (ICDE), 2006.

50. M. Kutsch, V. Markl, P. Hass, N. Megiddo, and T. M. Tran, "Integrating a Maximum-Entropy Cardinality Estimator Into DB2 UDB," Advances in Database Technology -- EDBT 2006 10 International Conference on Extending Database Technology, Munich, Germany, 26-31 March 2006, pp. 1092-1096.

51. V. Markl, M. Kutsch, T. M.Tran, P. J. Haas, and N. Megiddo, “MAXENT: consistent cardinality estimation in action,” Proceedings of the ACM SIGMOD International Conference on Management of Data, Chicago, Illinois, USA, June 27-29, 2006. ACM 2006, pp. 775-777.

52. E. Hazan and N. Megiddo, “Online Learning with Prior Knowledge,” in: Learning Theory, 20^th Annual Conference on Learning Theory, COLT 2007, San Diego, CA, June 2007, LNAI 4539, Springer, pp. 499-513.

53. N. Megiddo and V. Vazirani, "Continuity Properties of Equilibrium Prices and Allocations in Linear Fisher Markets," Proceedings of Internet and Network Economics, Third International Workshop, WINE 2007, San Diego, CA, USA, December 12-14, 2007, Lecture Notes in Computer Science 4858 Springer, 2007, pp. 362-367.

54. D. Dash, J. Rao, N. Megiddo, A. Ailamaki, and G. M. Lohman, Dynamic faceted search for discovery-driven analysis,” Proceedings of the 17th ACM Conference on Information and Knowledge Management, CIKM 2008, Napa Valley, California, USA, October 2008. ACM 2008, pp. 3-12.

55. H. Jin, J. Lotspiech and N. Megiddo, “Efficient Coalition Detection in Traitor Tracing,” Proceedings of The IFIP Tc 11 23^rd International Information Security Conference, 2008, pp.365-380.

56. H. Jin, J. Lotspiech, M. Nelson and N. Megiddo, “Adaptive Traitor Tracing for Large Anonymous Attack,” Proceedings of the 8th ACM workshop on Digital rights management, Alexandria, VA, USA, October 27, 2008, ACM 2008, pp. 1-8.

Technical Reports

1. N. Megiddo, "On the nucleolus of a composition of characteristic function games," Technical Report, Department of Mathematical Sciences, Tel Aviv University, 1973.

2. N. Megiddo, "A generalization of Eaves' odd theorem," Technical Report, Department of Statistics, Tel Aviv University, 1976.

3. N. Megiddo and S. L. Hakimi, "Pursuing mobile hiders in a graph," Discussion Paper No. 360, Center for Mathematical Studies in Economics and Management Science, Northwestern University, 1978.

4. N. Megiddo, "Applications of modern cryptography to secret voting," Technical Report, Department of Statistics, Tel Aviv University, 1980.

5. N. Megiddo, "An application of parallel computation to sequential computation: The problem of cost-effective resource allocation," TWISK 202, National Research Institute for Mathematical Sciences, Council for Scientific and Industrial Research (CSIR), Pretoria, South Africa, March 1981.

6. N. Megiddo, "Parallel algorithms for finding the maximum and the median almost surely in constant-time," Technical Report, Graduate School of Industrial Administration, Carnegie–Mellon University, October 1982.

7. N. Megiddo, "Poly-log parallel algorithms for LP with an application to exploding flying objects," Technical Report, Graduate School of Industrial Administration, Carnegie–Mellon University, November 1982.

8. N. Megiddo, "Recognizing 'digital disks'," manuscript, XEROX Palo Alto Research Center, 1984.

9. N. Megiddo, "A variation on Karmarkar's algorithm," manuscript, IBM San Jose Research Laboratory, San Jose, California, 1984.

10. N. Megiddo, "A note on sensitivity analysis in algebraic algorithms," Research Report RJ 4958, IBM Almaden Research Center, San Jose, California, 1985.

11. N. Megiddo and E. Zemel, "A randomizing O(n log n) algorithm for the weighted Euclidean 1-center problem," Research Report RJ 5005, IBM Almaden Research Center, San Jose, California, 1985.

12. N. Megiddo, "Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm," Research Report RJ 4962, IBM Almaden Research Center, San Jose, California, 1985.

13. N. Megiddo, "Dynamic location problems," Research Report RJ 4983, IBM Almaden Research Center, San Jose, California, 1986.

14. J. O'Rourke, S. R. Kosaraju and N. Megiddo, "Computing circular separability," Research Report RJ 4986, IBM Almaden Research Center, San Jose, California, 1986.

15. N. Megiddo, "A note on degeneracy in linear programming," Research Report RJ 4895, IBM Almaden Research Center, San Jose, California, 1985.

16. N. Megiddo and A. Wigderson, "On play by means of computing machines," Research Report RJ 4984, IBM Almaden Research Center, San Jose, California, 1986.

17. N. Megiddo, "Remarks on bounded rationality," Research Report RJ 5270, IBM Almaden Research Center, San Jose, California, 1986.

18. N. Megiddo, "Introduction: New approaches to linear programming," Research Report RJ 5278, IBM Almaden Research Center, San Jose, California, 1986.

19. N. Megiddo, "Linear programming (1986)," Research Report RJ 5405, IBM Almaden Research Center, San Jose, California, 1986.

20. N. Megiddo, "On the complexity of linear programming," Research Report RJ 4985, IBM Almaden Research Center, San Jose, California, 1986.

21. N. Megiddo, "Are the vertex cover and the dominating set problems equally hard?," Research Report RJ 5783, IBM Almaden Research Center, San Jose, California, 1987.

22. N. Megiddo, "Pathways to the optimal set in linear programming,"  Research Report RJ 5295, IBM Almaden Research Center, San Jose, California, 1986.

23. N. Megiddo, "A note on Karmarkar's projective transformation," IBM Almaden Research Center, San Jose, California, , December 1988.

24. N. Megiddo, "On the complexity of polyhedral separability," Research Report RJ 5252, IBM Almaden Research Center, San Jose, California, 1986.

25. N. Megiddo, "Extending NC and RNC algorithms," Research Report RJ 5294, IBM Almaden Research Center, San Jose, California, 1986.

26. N. Megiddo and M. Shub, "Boundary behavior of interior point algorithms in linear programming," Research Report RJ 5319, IBM Almaden Research Center, San Jose, California, 1986.

27. R. Hassin and N. Megiddo, "Approximation algorithms for hitting objects by straight lines," Research Report RJ 5659, IBM Almaden Research Center, San Jose, California, 1987.

28. N. Megiddo, "On the complexity of some geometric problems in unbounded dimension," Research Report RJ 5744, IBM Almaden Research Center, San Jose, California, 1987.

29. N. Megiddo and U. Vishkin, "On finding a minimum dominating set in a tournament," Research Report RJ 5745, IBM Almaden Research Center, San Jose, California, 1987.

30. N. Megiddo, "On the ball spanned by balls," Research Report RJ 5763, IBM Almaden Research Center, San Jose, California, 1987.

31. N. Megiddo, "On the complexity of solving the generalized set packing problem approximately," Research Report RJ 5898, IBM Almaden Research Center, San Jose, California, 1987.

32. R. Hassin and N. Megiddo, "On orientations and shortest paths," Research Report RJ 6008, IBM Almaden Research Center, San Jose, California, 1987.

33. N. Megiddo, "On computable beliefs of rational machines," Research Report RJ 6108, IBM Almaden Research Center, San Jose, California, 1988.

34. R. Fagin, J. Y. Halpern and N. Megiddo, "A logic for reasoning about probabilities," Research Report RJ 6190, IBM Almaden Research Center, San Jose, California, 1988.

35. N. Megiddo, "Switching from a primal-dual Newton algorithm to a primal-dual (interior) simplex algorithm," Research Report RJ 6327, IBM Almaden Research Center, San Jose, California, 1988.

36. N. Megiddo, "On finding primal- and dual-optimal bases," Research Report RJ 6328, IBM Almaden Research Center, San Jose, California, 1988.

37. N. Megiddo, "On finding additive, superadditive and subadditive set-functions subject to linear inequalities," Research Report RJ 6329, IBM Almaden Research Center, San Jose, California, 1988.

38. N. Megiddo and R. Chandrasekaran, "On the epsilon-perturbation method for avoiding degeneracy," Research Report RJ 6330, IBM Almaden Research Center, San Jose, California, 1988.

39. N. Megiddo, "A Note on the Complexity of P-Matrix LCP and Computing an Equilibrium," Research Report RJ 6439, IBM Almaden Research Center, San Jose, California, 1988.

40. N. Megiddo, "On solving the linear programming problem approximately," Research Report RJ 6485, IBM Almaden Research Center, San Jose, California, 1988.

41. M. Kojima, N. Megiddo and Y. Ye, "An interior point potential reduction algorithm for the linear complementarity problem," Research Report RJ 6486, IBM Almaden Research Center, San Jose, California, 1988.

42. G. S. Lueker, N. Megiddo and V. Ramachandran, "Linear programming with two variables per inequality in poly log time," Research Report RJ 6491, IBM Almaden Research Center, San Jose, California, 1988.

43. R. Hassin and N. Megiddo, "Exact computation of optimal inventory policies over an unbounded horizon,"   Research Report RJ 6492, IBM Almaden Research Center, San Jose, California, 1988.

44. M. Kojima, N. Megiddo and T. Noma, "Homotopy continuation methods for nonlinear complementarity problems," Research Report RJ 6638, IBM Almaden Research Center, San Jose, California, 1988.

45. N. Megiddo, "On probabilistic machines, bounded rationality, and average-case complexity," Research Report RJ 7039, IBM Almaden Research Center, San Jose, California, 1989.

46. M. Kojima and N. Megiddo, "The relation between the path of centers and Smale's regularization of the linear programming problem," Research Report RJ 7069, IBM Almaden Research Center, San Jose, California, 1989.

47.  N. Megiddo and C.H. Papadimitriou, "A note on total functions, existence theorems and complexity," Research Report RJ 7091, IBM Almaden Research Center, San Jose, California, 1989.

48. N. Alon and N. Megiddo, "Parallel linear programming in fixed dimension almost surely in constant time," Research Report RJ 7245, IBM Almaden Research Center, San Jose, California, 1990.

49. E. Cohen and N. Megiddo, "Recognizing properties of periodic graphs," Research Report RJ 7246, IBM Almaden Research Center, San Jose, California, 1990.

50. M. Kojima, N. Megiddo, T. Noma and A. Yoshise, "A unified approach to interior point algorithms for linear complementarity problems," Research Report RJ 7493, IBM Almaden Research Center, San Jose, California, 1990.

51. E. Cohen and N. Megiddo, "Strongly polynomial-time and NC algorithms for detecting cycles in dynamic graphs," Research Report RJ 7587, IBM Almaden Research Center, San Jose, California, 1990.

52. E. Cohen and N. Megiddo, "Algorithms and and complexity analysis of some flow problems," Research Report RJ 7626, IBM Almaden Research Center, San Jose, California, 1990.

53. E. Cohen and N. Megiddo, "Maximizing concave functions in fixed dimension," Research Report RJ 7656, IBM Almaden Research Center, San Jose, California, 1990.

54. N. Megiddo, "A general NP-completeness theorem," Research Report RJ 7677, IBM Almaden Research Center, San Jose, California, 1990.

55. M. Kojima, N. Megiddo and S. Mizuno, "A general framework of continuation methods for complementarity problems," Research Report RJ 7720, IBM Almaden Research Center, San Jose, California, 1990.

56. D. Koller and N. Megiddo, "The complexity of two-person zero-sum games in extensive form," Research Report RJ 7837, IBM Almaden Research Center, San Jose, California, 1990.

57. M. Kojima, N. Megiddo and S. Mizuno, "Theoretical convergence of large-step primal-dual interior point algorithms for linear programming," Research Report RJ 7872, IBM Almaden Research Center, San Jose, California, 1990.

58. E. Cohen and N. Megiddo, "Improved algorithms for linear inequalities with two variables per inequality," Research Report RJ 8187, IBM Almaden Research Center, San Jose, California, 1991.

59. E. Cohen and N. Megiddo, "New algorithms for generalized network flows," Research Report RJ 8188, IBM Almaden Research Center, San Jose, California, 1991.

60. D. Koller and N. Megiddo, "Finding mixed strategies with small supports in extensive form games," Research Report RJ 8380, IBM Almaden Research Center, San Jose, California, 1991.

61. M. Kojima, N. Megiddo and S. Mizuno, "A primal-dual exterior point algorithm for linear programming," Research Report RJ 8500, IBM Almaden Research Center, San Jose, California, 1991.

62. N. Megiddo and A. Tamir, "Linear time algorithms for some separable quadratic programming problems," Research Report RJ 8501, IBM Almaden Research Center, San Jose, California, 1991.

63. M. Kojima, N. Megiddo and S. Mizuno, "A conjugate direction method for approximating the analytic center of a polytope," Research Report RJ 8540, IBM Almaden Research Center, San Jose, California, 1991.

64. D. Koller and N. Megiddo, "Constructing small sample spaces satisfying given constraints," Research Report RJ 8597, IBM Almaden Research Center, San Jose, California, 1992.

65. N. Megiddo, "A note on approximate linear programming," Research Report RJ 8634, IBM Almaden Research Center, San Jose, California, 1992.

66. N. Megiddo, "The least index pivot rule with randomly permuted columns," Research Report RJ 9072, IBM Almaden Research Center, San Jose, California, 1992.

67. M. Kojima, N. Megiddo, and S. Mizuno, "A Lagrangian relaxation method for approximating the analytic center of a polytope," Research Report RJ 9075, IBM Almaden Research Center, San Jose, California, 1992.

68. T. Hegedus and N. Megiddo, "On the Geometric Separability of Boolean Functions," Research Report RJ 9147, IBM Almaden Research Center, San Jose, California, 1992.

69. M. Ajtai and N. Megiddo, "A deterministic  poly(log log n)-time n-processor algorithm for linear programming in fixed dimension," Research Report RJ 9204, IBM Almaden Research Center, San Jose, California, 1993.

70. P. Beling and N. Megiddo, "Using fast matrix multiplication to find basic solutions," Research Report RJ 9234, IBM Almaden Research Center, San Jose, California, 1993.

71. T. Feder, N. Megiddo, and S. A. Plotkin, "A sublinear parallel algorithm for stable matching," Research Report RJ 9327, IBM Almaden Research Center, San Jose, California, 1993.

72. M. Kojima, N. Megiddo, S. Mizuno and S. Shindoh, "Horizontal and Vertical Decomposition in Interior-Point Methods for Linear Programming" Research Report RJ 9901, IBM Almaden Research Center, San Jose, California, 1994.

73. D. Koller, N. Megiddo and B. von Stengel, "Efficient computation of equilibria for extensive two-person games," Research Report RJ 9907, IBM Almaden Research Center, San Jose, California, 1994.

74. N. Megiddo, M. Naor, and D. P. Anderson, "The minimum reservation rate problem in digital audio/video systems," Research Report RJ 9917, IBM Almaden Research Center, San Jose, California, 1994.

75. M. Ajtai, N. Megiddo and O. Waarts, "Improved algorithms and analysis for secretary problems and generalizations," Research Report RJ 9968, IBM Almaden Research Center, San Jose, California, 1995.

76. N. Megiddo, S. Mizuno and T. Tsuchiya, "A linear programming instance with many crossover events," Research Report RJ 9978, IBM Almaden Research Center, San Jose, California, 1995.

77. N. Megiddo, "Finding a line of sight through boxes in d-space in linear time," Research Report RJ 10018, IBM Almaden Research Center, San Jose, California, 1996.

78. S. Mizuno, T. Tsuchiya and N. Megiddo, "A modified layered-step interior-point algorithm for linear programming," Research Report 10028, IBM Almaden Research Center, San Jose, California, 1996.

79. S. Juge, N. Megiddo and E. Schraner, "Simulation and Optimization of HDA Testing'', Research Report RJ 10037, IBM Almaden Research Center, San Jose, CA 1996.

80. N. Megiddo, "Toll Savings in the Operation of ISDN Lines,'' Research Report RJ 10053, IBM Almaden Research Center, San Jose, CA 1996.

81. N. Megiddo, "The Variance of the Gini Index Estimator,'' Research Report RJ 10054, IBM Almaden Research Center, San Jose, CA 1996.

82. C.-T. Ho, R. Agrawal, N. Megiddo and R. Srikant, "Range queries in OLAP data cubes," Research Report RJ 10070, IBM Almaden Research Center, San Jose, CA 1997.

83. C.-T. Ho, N. Megiddo, and J. J. Tsay, "Fast algorithms for range-max queries in OLAP data cubes," Research Report RJ 10071, IBM Almaden Research Center, San Jose, CA 1997.

84. N. Megiddo and U. Shaft, "Efficient nearest neighbor indexing based on a collection of space filling curves," Research Report RJ 10093, IBM Almaden Research Center, San Jose, CA, 1997.

85. N. Megiddo, "On structured Markov decision processes in continuous state space," Research Report RJ 10264, IBM Almaden Research Center, San Jose, CA, 2000.

86. J. Rao, C. Zhang, G. M. Lohman, and N. Megiddo, "Automating Physical Database Design in a Parallel Database: The DB2 Partitioning Advisor," Research Report RJ 10208, IBM Almaden Research Center, San Jose, CA, 2001.

87. J. Rao, C. Zhang, G. M. Lohman, and N. Megiddo, "Automating Physical Database Design in a Parallel Database," Research Report RJ 10225, IBM Almaden Research Center, San Jose, CA, 2001.

88. F. Naumann, C. T. Ho, X. Tian, L. Haas and N. Megiddo "Attribute Classification Using Feature Analysis," Research Report RJ 10264, IBM Almaden Research Center, San Jose, CA, 2002.

89. N. Megiddo and D. S. Modha, "A Simple Adaptive Cache Algorithm Outperforms LRU," Research Report RJ 10284, IBM Almaden Research Center, San Jose, CA, 2003.

90. N. Megiddo, “Formation of Preferences and Strategic Analysis: Can they be De-Coupled?” 9/24/2003. Presented at IMGTA'2001- XIV Italian Meeting on Game Theory and Applications.

91. N. Megiddo and D. S. Modha, "One Up on LRU," Research Report RJ 10285, IBM Almaden Research Center, San Jose, CA, 2003.

92. H. Jin, J. Lotspiech, and N. Megiddo, “Efficient Traitor Tracing,” Research Report RJ 10390, IBM Almaden Research Center, San Jose, CA, 10/03/2006.

93. E. Hazan and N. Megiddo, “The "Arrangement Method" for Linear Programming is Equivalent to the Phase-One Method,” Research Report RJ 10414, IBM Almaden Research Center, San Jose, CA, 8/28/2007.

Book review

Tree Network and Planar Rectilinear Location Theory. By A. J. W. Kolen., SIAM Review 30 (1988), No. 2, pp. 340–341.

Patents

• "METHOD FOR CREATING AND MAINTAINING THREADS OF PHONE/EMAIL/FAX/SMS CONVERSATIONS" (with A. Amir), U.S. 7,539,295, 5/26/2009.
• "CONSISTENT AND UNBIASED CARDINALITY ESTIMATION FOR COMPLEX QUERIES WITH CONJUNCTS OF PREDICATES" (with P. Haas, M. Kutsch, and V. Markl), U.S. 7,512,629, 3/31/2009.
• "CONSISTENT HISTOGRAM MAINTENANCE USING QUERY FEEDBACK" (with P. Haas and V. Markl), U.S. 7,512,574, 3/31/2009.
• "COMPUTER AUTOMATED DISCOVERY OF INTERESTINGNESS IN FACETED SEARCH (with D. Dash, G. M. Lohman, and J. Rao) U. S. 7,493,319, 2/17/2009.
• "SYSTEM, METHOD AND PROGRAM PRODUCT FOR AUTOMATICALLY MANAGING CONTRACTS", U.S. 7,480,621, 1/20/2009.
• "DISCOVERING INTERESTINGNESS IN ADVANCED FACETED SEARCH" (with D. Dash, G. Lohman, and J. Rao) U.S. 7,392,250, 6/24/2008.
• "SELECTIVITY ESTIMATION FOR CONJUNCTIVE PREDICATES IN THE PRESENCE OF PARTIAL KNOWLEDGE ABOUT MULTIVARIATE DATA DISTRIBUTIONS" (with M. Kutsch, V. Markl, and T.M. Tran), U.S. 7,376,639, 5/20/2008.
• "METHOD AND SYSTEM FOR SEARCHING AND RETRIEVING DOCUMENTS" (with A. Tomkins and S. Vaithyanathan), U.S. 7,209,913, 4/24/2007.

• "SYSTEM AND METHOD FOR ADAPTIVELY MANAGING PAGES IN A MEMORY" (with D. MODHA), U.S. 7,167,953, 1/23/2007.
• "METHOD FOR SOLVING STOCHASTIC CONTROL PROBLEMS OF LINEAR SYSTEMS IN HIGH DIMENSION", U.S. 7,117,130, 10/3/2006.
• "MASSIVLEY COMPUTATIONAL PARALLIZABLE OPTIMIZATION MANAGEMENT SYSTEM AND METHOD",  U.S. 7,013,344, 3/14/2006.
• "SYSTEM AND METHOD FOR IMPLEMENTING AN ADAPTIVE REPLACEMENT CACHE POLICY" (with D. MODHA), U.S. 6,996,676, 2/7/2006.
• "SYSTEM AND METHOD FOR GATHERING, INDEXING, AND SUPPLYING PUBLICLY AVAILABLE DATA CHARTS" (with S. Vaithyanathan), U.S. 6,996,268, 2/7/2006.
• "SYSTEM, METHOD AND PROGRAM PRODUCT FOR AUTOMATICALLY MANAGING CONTRACTS", U.S. 6,985,868 B1, 1/10/2006.
• "EFFICIENT RETRIEVAL OF UNIFORM RESOURCE LOCATORS" (with K. McCurley), U.S. 6,957,224, 10/18/2005.
• "METHOD FOR ASSIGNING ENCRYPTION KEYS" (with D. Naor, J. B. Lotspiech, S. Naor and R. Fagin), U.S. 6,947,563, 9/20/2005.
• "METHOD AND PROGRAM PRODUCT FOR MAINTAINING SECURITY OF PUBLICLY DISTRIBUTED INFORMATION" (with D. Modha), U.S.6,947,557, 9/20/2005.
• "SYSTEM AND METHOD FOR PROFILING ACCESS TO DISK DRIVE COMMANDS BASED ON A DUAL SERVO MODE MODEL", U.S. 6,898,665, 5/24/2005.
• "SYSTEM AND METHOD FOR IMPROVING THE EFFECTIVENESS OF WEB ADVERTISING" (with X. Zhu), China, ZL0113259, 1/5/2005; U.S. 6,892,181, 5/10/2005, Singapore 102634, 5/31/2005.
• "METHOD AND APPARATUS FOR REPRESENTING DATABASE AND QUERY INFORMATION USING THE INTERVAL HASH TREE" (with P. Raghavan and T.F. Syeda-Mahmood), U.S. 6,757,686, 6/29/2004.
• "SYSTEM FOR SECURING ELECTRONIC MAIL", U.S. 6,745,231, 6/1/2004.
• "RESTRUCTURING OF EXECUTABLE COMPUTER CODE AND LARGE DATA SETS" (with B. Mendelson), U.S. 6,742,179, 5/25/2004.
• "SYSTEM AND METHOD FOR MAINTAINING MULTIPLE IDENTITIES AND REPUTATIONS FOR INTERNET INTERACTIONS", U.S. 6,725,269, 4/20/2004.
• "METHOD FOR SOLVING A LARGE SPARSE TRIANGULAR SYSTEM OF LINEAR EQUATIONS" (with J.J. Forrest and J.A. Tomlin), U.S. 6,694,343, 2/17/2004.
• "DIGITAL PEN USING SPECKLE TRACKING" (with R. Fagin, R.J.T. Morris, S. Rajagopalan, H.J. Rosen and T.G. Zimmerman), U.S. 6,686,579, 2/3/2004.
• "SMOOTH END OF AUCTION ON THE INTERNET", U.S. 6,665,649, 12/16/2003.
• "SYSTEM, METHOD AND PROGRAM PRODUCT FOR SOFTWARE DEVELOPMENT" (with X. Zhu), U.S. 6,658,642, 12/3/2003.
• "NON-INTERFERING SEEK BEHAVIOR MODIFICATION FOR IMPROVED HARD DRIVE PERFORMANCE" (with S.W. Ng), U.S. 6,658,535, 12/2/2003.
• "SYSTEM AND METHOD FOR SCHEDULING DISK DRIVE COMMANDS BY EXPECTED TOTAL ACCESS TIME", U.S. 6,574,676, 6/3/2003.
• "SYSTEM AND METHOD FOR GROUPING DISK ACCESS COMMANDS IN A QUEUE ACCORDING TO PROXIMATE DISK POSITIONS", U.S. 6,571,298, 5/27/2003.
• "SYSTEM AND METHODOLOGY FOR VIDEO CONFERENCING AND INTERNET CHATTING IN A COCKTAIL PARTY STYLE", U.S. 6,559,863, 5/6/2003.
• "SYSTEM AND METHOD FOR DISCOVERING PREDICTIVE ASSOCIATION RULES" (with R. Srikant), U.S. 6,182,070, 1/30/2001.
• "METHOD FOR COMPUTING NEAR NEIGHBORS OF A QUERY POINT IN A DATABASE" (with U. Shaft), U.S. 6,148,295, 11/14/2000.
• "METHOD OF, SYSTEM FOR, AND COMPUTER PROGRAM PRODUCT FOR PERFORMING WEIGHTED LOOP FUSION BY AN OPTIMIZING COMPILER" (with V. Sarkar), U.S. 6,058,266, 5/2/2000.
• "METHOD LOOP EXECUTION TIME BY OPTIMIZING BLOCK/TILE SIZES" (with V. Sarkar), U.S. 5,953,531, 9/14/1999.
• "METHOD AND SYSTEM FOR PERFORMING RANGE MAX/MIN QUERIES ON A DATA CUBE" (with C.T. Ho and R. Agrawal), U.S. 5,926,820, 7/20/1999.
• "FAST QUERY SEARCH IN LARGE DIMENSION DATABASE" (with J. L. Hafner and E. Upfal), U.S. 5,848,404, 12/8/1998.
• "PROGRAM PRODUCT FOR DISPLAYING A LINE PASSING THROUGH A PLURALITY OF BOXES", U.S. 5,533,178, 7/2/1996.
• "METHOD AND APPARATUS FOR DISPLAYING A LINE PASSING THROUGH A PLURALITY OF BOXES", U.S. 5,481,658, 1/2/1996.
• "METHOD AND DEVICE FOR FINDING OUT LINE THROUGH AXIAL BOX IN THREE-DIMENSION AND HIGHER DIMENSION", Japan 07105403A2, 04/21/1995.
• "SYSTEM FOR ENHANCING BUYERS PERFORMANCE IN ELECTRONIC COMMERCE", patent pending.
• "SYSTEM, METHOD AND PROGRAM PRODUCT FOR INCREASING THE EFFECTIVENESS OF AUDIO AND VIDEO BROADCASTING", patent pending.
• "SYSTEM AND METHOD FOR AUTONOMIC OPTIMIZAITON BY COMPUTER PROGRAMS", patent pending.
• "SYSTEM AND METHOD FOR AUTOMATING DATA PARTITIONING IN A PARALLEL DATABASE" (with G. Lohman, J. Rao and C. Zhang), patent pending.
• "BUFFERED VIEWING OF ELECTRONIC DOCUMENTS" (with A. Amir), patent pending.
• "COMPUTER SYSTEM MANAGEMENT AND THROUGHPUT MAXIMIZATION UNDER PEAK POWER CONSTRAINTS" (with R. Krauthgamer), patent pending.
• "AUTOMATICALLY AND ADAPTIVELY DETERMINING EXECUTION PLANS FOR QUERIES WITH PARAMETER MARKERS" (with W. Fan, G. Lohman, V. Markl, J. Rao, and D. Simmen), patent pending.
• "METHOD FOR OPERATING AND MANAGING A RE-FUELING BUSINESS", patent pending.
• "METHOD FOR MACHINE LEARNING WITH STATE INFORMATION" (with E. Hazan), patent pending.
• "METHOD AND APPARATUS FOR COLLABORATIVE SELECTION OF PROPOSALS", patent pending.
• "A METHOD FOR DYNAMICALLY FREEING UP COMPUTER RESOURCES" (with A. Amir), patent pending.
• "ADAPTIVE TRAITOR TRACING" (with H. Jin, J. Lotspiech, and M.J. Nelson), patent pending.

---

Last updated May 28, 2009.