Nimrod Megiddo () is a

mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, mathematical structure, structure, space, Mathematica ...

and

computer scientist A computer scientist is a scientist who specializes in the academic study of computer science. Computer scientists typically work on the theoretical side of computation. Although computer scientists can also focus their work and research on ...

. He is a research scientist at the

IBM International Business Machines Corporation (using the trademark IBM), nicknamed Big Blue, is an American Multinational corporation, multinational technology company headquartered in Armonk, New York, and present in over 175 countries. It is ...

Almaden Research Center and

Stanford University Leland Stanford Junior University, commonly referred to as Stanford University, is a Private university, private research university in Stanford, California, United States. It was founded in 1885 by railroad magnate Leland Stanford (the eighth ...

. His interests include

combinatorial optimization Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combina ...

algorithm In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...

design and analysis,

game theory Game theory is the study of mathematical models of strategic interactions. It has applications in many fields of social science, and is used extensively in economics, logic, systems science and computer science. Initially, game theory addressed ...

, and

machine learning Machine learning (ML) is a field of study in artificial intelligence concerned with the development and study of Computational statistics, statistical algorithms that can learn from data and generalise to unseen data, and thus perform Task ( ...

. He was one of the first people to propose a solution to the

bounding sphere In mathematics, given a non-empty set of objects of finite extension in d-dimensional space, for example a set of points, a bounding sphere, enclosing sphere or enclosing ball for that set is a d-dimensional solid sphere containing all of these ...

and

smallest-circle problem The smallest-circle problem (also known as minimum covering circle problem, bounding circle problem, least bounding circle problem, smallest enclosing circle problem) is a computational geometry problem of computing the smallest circle that cont ...

Education

Megiddo received his

PhD A Doctor of Philosophy (PhD, DPhil; or ) is a terminal degree that usually denotes the highest level of academic achievement in a given discipline and is awarded following a course of graduate study and original research. The name of the deg ...

in mathematics from the

Hebrew University of Jerusalem The Hebrew University of Jerusalem (HUJI; ) is an Israeli public university, public research university based in Jerusalem. Co-founded by Albert Einstein and Chaim Weizmann in July 1918, the public university officially opened on 1 April 1925. ...

for research supervised by

Michael Maschler Michael Bahir Maschler (; July 22, 1927 – July 20, 2008) was an Israeli mathematician well known for his contributions to the field of game theory. He was a professor in the Einstein Institute of Mathematics and the Center for the Study of ...

Career and research

In computational geometry, Megiddo is known for his

prune and search Prune and search is a method of solving optimization problems suggested by Nimrod Megiddo in 1983.Nimrod Megiddo (1983) Linear-time algorithms for linear programming in R3 and related problems. SIAM J. Comput., 12:759–776 The basic idea of ...

and parametric search techniques both suggested in 1983Nimrod Megiddo (1983) Linear-time algorithms for linear programming in R³ and related problems. SIAM J. Comput., 12:759–776 and used for various computational geometric optimization problems, in particular to solve the

linear time In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations ...

. His former doctoral students include

Edith Cohen Edith Cohen (Hebrew: אדית כהן; born May 21, 1966) is an Israeli and American computer scientist specializing in data mining and algorithms for big data. She is also known for her research on peer-to-peer networks. She works for Google in M ...

Awards and honours

Megiddo received the 2014 John von Neumann Theory Prize, the 1992 ICS Prize, and is a 1992 Frederick W. Lanchester Prize recipient. In 2009 he received the

Institute for Operations Research and the Management Sciences The Institute for Operations Research and the Management Sciences (INFORMS) is an international society for practitioners in the fields of operations research Operations research () (U.S. Air Force Specialty Code: Operations Analysis), often s ...

(INFORMS)

Fellow A fellow is a title and form of address for distinguished, learned, or skilled individuals in academia, medicine, research, and industry. The exact meaning of the term differs in each field. In learned society, learned or professional society, p ...

s award for contributions to the theory and application of mathematical programming, including parametric searches, interior point methods, low dimension Linear Programming, probabilistic analysis of the simplex method and computational game theory.

References

{{DEFAULTSORT:Megiddo, Nimrod Year of birth missing (living people) Living people Researchers in geometric algorithms Hebrew University of Jerusalem alumni American computer scientists American operations researchers Israeli operations researchers John von Neumann Theory Prize winners Game theorists Numerical analysts Fellows of the Institute for Operations Research and the Management Sciences Jewish scientists Israeli systems scientists