Jack Edmonds

from Wikipedia, the free encyclopedia
Jack Edmonds

Jack R. Edmonds (born April 5, 1934 ) is a Canadian computer scientist and mathematician who deals with combinatorial optimization .

Edmonds studied at George Washington University with a bachelor's degree in 1958 and at the University of Maryland with a master's degree in 1959. He then worked until 1969 in the Operations Research department at the National Bureau of Standards under Alan Goldman . From 1969 he was a professor at the University of Waterloo . He taught there until his retirement in 1999, except for a period from 1991 to 1993 when he was involved in a dispute with the university about an alleged resignation letter.

He and Richard M. Karp created the Edmonds and Karp algorithm . In 1965 he published the first polynomial-time algorithm for the matching problem in graph theory (Edmonds' algorithm). He is also known for the structure theorem by Tibor Gallai and Edmonds (and Edmonds-Gallai decomposition), which describes maximum matchings, for contributions to the theory of matroids and optimal branchings.

With Ellis L. Johnson he solved the postman problem ( Chinese Postman Problem ) with matching methods. They showed that it was solvable in polynomial time (as opposed to the seemingly similar but far more difficult traveling salesman problem ).

In 1985 he received the John von Neumann Theory Prize .

literature

  • David R. Lid (Editor): A century of excellence in standards, measurement and technology: a chronicle of selected NBS / NIST 1901-2000 , NIST Special Publications 958, Washington DC 2001

Fonts

  • Paths, trees and flowers, Canadian Journal of Mathematics, Volume 17, 1965, pp. 449-467
  • Matroids and the Greedy algorithm, Mathematical Programming, Volume 1, 1971, pp. 127-136
  • with Richard Karp: Theoretical improvements in the algorithmic efficiency of network flow algorithms, Journal of the ACM, Volume 19, 1972, pp. 248-264

Individual evidence

  1. ^ Edmonds, Johnson Matching, Euler tours and the Chinese Postman , Mathematical Programming, Vol. 5, 1973, pp. 88-124
personal data
SURNAME Edmonds, Jack
ALTERNATIVE NAMES Edmonds, Jack R.
BRIEF DESCRIPTION Canadian mathematician and computer scientist
DATE OF BIRTH April 5, 1934