, birth_date = , birth_place = , death_date = , death_place = , citizenship = , field =

Operations research Operations research ( en-GB, operational research) (U.S. Air Force Specialty Code: Operations Analysis), often shortened to the initialism OR, is a discipline that deals with the development and application of analytical methods to improve decis ...

Algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...

s
Complexity

Machine learning Machine learning (ML) is a field of inquiry devoted to understanding and building methods that 'learn', that is, methods that leverage data to improve performance on some set of tasks. It is seen as a part of artificial intelligence. Machine ...

Game theory , workplaces =

IBM Research IBM Research is the research and development division for IBM, an American multinational information technology company headquartered in Armonk, New York, with operations in over 170 countries. IBM Research is the largest industrial research or ...

Stanford University , alma_mater = Hebrew University of Jerusalem , thesis_title = Compositions of Cooperative Games , thesis_year = 1972 , doctoral_advisor = Michael Maschler , doctoral_students =

Edith Cohen Edith Cohen (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 Mountain View, California, ...

, known_for =

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 t ...

, prizes = Frederick W. Lanchester Prize (1992)

John von Neumann Theory Prize The John von Neumann Theory Prize of the Institute for Operations Research and the Management Sciences (INFORMS) is awarded annually to an individual (or sometimes a group) who has made fundamental and sustained contributions to theory in operat ...

(2014) , website = Nimrod Megiddo ( he, נמרוד מגידו) 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, structure, space, models, and change. History On ...

and

computer scientist A computer scientist is a person who is trained in the academic study of computer science. Computer scientists typically work on the theoretical side of computation, as opposed to the hardware side on which computer engineers mainly focus (al ...

. He is a research scientist at the IBM

Almaden Research Center IBM Research is the research and development division for IBM, an American multinational information technology company headquartered in Armonk, New York, with operations in over 170 countries. IBM Research is the largest industrial research org ...

and Stanford University. 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 combi ...

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...

design and analysis,

game theory Game theory is the study of mathematical models of strategic interactions among rational agents. Myerson, Roger B. (1991). ''Game Theory: Analysis of Conflict,'' Harvard University Press, p.&nbs1 Chapter-preview links, ppvii–xi It has appli ...

, and

machine learning Machine learning (ML) is a field of inquiry devoted to understanding and building methods that 'learn', that is, methods that leverage data to improve performance on some set of tasks. It is seen as a part of artificial intelligence. Machine ...

. 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 an d-dimensional solid sphere containing all of the ...

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 mathematical problem of computing the smallest circle that contains all o ...

Education

Megiddo received his PhD in mathematics from the Hebrew University of Jerusalem for research supervised by Michael Maschler.

Career and research

computational geometry Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems ar ...

, 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 t ...

and

parametric search In the design and analysis of algorithms for combinatorial optimization, parametric search is a technique invented by for transforming a decision algorithm (does this optimization problem have a solution with quality better than some given thres ...

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 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 performed by ...

. His former doctoral students include

Awards and honours

Megiddo received the 2014

, 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 (O.R.), management science, and analytics. It was established in 1995 with the merger of ...

(INFORMS)

Fellow A fellow is a concept whose exact meaning depends on context. In learned or professional societies, it refers to a privileged member who is specially elected in recognition of their work and achievements. Within the context of higher education ...

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 systems scientists