Leonid Genrikhovich Khachiyan
(;
russian: Леони́д Ге́нрихович Хачия́н; May 3, 1952April 29, 2005) was a Soviet and American mathematician 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 (a ...
.
He was most famous for his
ellipsoid algorithm (1979) for
linear programming
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is ...
, which was the first such
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 ...
known to have a
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exampl ...
running time. Even though this algorithm was shown to be impractical, it has inspired other
randomized algorithm
A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performa ...
s for
convex programming
Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets (or, equivalently, maximizing concave functions over convex sets). Many classes of convex optimization pro ...
and is considered a significant theoretical breakthrough.
Early life and education
Khachiyan was born on May 3, 1952, in
Leningrad
Saint Petersburg ( rus, links=no, Санкт-Петербург, a=Ru-Sankt Peterburg Leningrad Petrograd Piter.ogg, r=Sankt-Peterburg, p=ˈsankt pʲɪtʲɪrˈburk), formerly known as Petrograd (1914–1924) and later Leningrad (1924–1991), i ...
to
Armenian parents Genrikh Borisovich Khachiyan, a mathematician and professor of
theoretical mechanics, and Zhanna Saakovna Khachiyan, a
civil engineer
A civil engineer is a person who practices civil engineering – the application of planning, designing, constructing, maintaining, and operating infrastructure while protecting the public and environmental health, as well as improving existing ...
.
His grandparents were
Karabakh
Karabakh ( az, Qarabağ ; hy, Ղարաբաղ, Ġarabaġ ) is a geographic region in present-day southwestern Azerbaijan and eastern Armenia, extending from the highlands of the Lesser Caucasus down to the lowlands between the rivers Kura and ...
Armenians.
He had two brothers: Boris and Yevgeniy (Eugene).
His family moved to
Moscow
Moscow ( , US chiefly ; rus, links=no, Москва, r=Moskva, p=mɐskˈva, a=Москва.ogg) is the capital and largest city of Russia. The city stands on the Moskva River in Central Russia, with a population estimated at 13.0 million ...
in 1961, when he was nine.
He received a master's degree from the
Moscow Institute of Physics and Technology
Moscow Institute of Physics and Technology (MIPT; russian: Московский Физико-Технический институт, also known as PhysTech), is a public research university located in Moscow Oblast, Russia. It prepares speciali ...
.
In 1978 he earned his Ph.D. in
computational mathematics
Computational mathematics is an area of mathematics devoted to the interaction between mathematics and computer computation.National Science Foundation, Division of Mathematical ScienceProgram description PD 06-888 Computational Mathematics 2006 ...
/
theoretical mathematics from the
Computer Center of the Soviet Academy of Sciences and in 1984 a D.Sc. in
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
from the same institution.
Career
Khachiyan began his career at the Soviet Academy of Sciences,
working as a researcher at the academy's
Computer Center in Moscow.
He also worked as an
adjunct professor
An adjunct professor is a type of academic appointment in higher education who does not work at the establishment full-time. The terms of this appointment and
the job security of the tenure vary in different parts of the world, however the genera ...
at the
Moscow Institute of Physics and Technology
Moscow Institute of Physics and Technology (MIPT; russian: Московский Физико-Технический институт, also known as PhysTech), is a public research university located in Moscow Oblast, Russia. It prepares speciali ...
.
In 1979 he stated: "I am a theoretical mathematician and I'm just working on a class of very difficult mathematical problems."
Khachiyan immigrated to the United States in 1989.
He first taught at
Cornell University
Cornell University is a private statutory land-grant research university based in Ithaca, New York. It is a member of the Ivy League. Founded in 1865 by Ezra Cornell and Andrew Dickson White, Cornell was founded with the intention to tea ...
as a visiting professor. In 1990 he joined
Rutgers University
Rutgers University (; RU), officially Rutgers, The State University of New Jersey, is a public land-grant research university consisting of four campuses in New Jersey. Chartered in 1766, Rutgers was originally called Queen's College, and was ...
as a visiting professor.
He became
professor
Professor (commonly abbreviated as Prof.) is an academic rank at universities and other post-secondary education and research institutions in most countries. Literally, ''professor'' derives from Latin as a "person who professes". Professo ...
of
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
at Rutgers in 1992.
By 2005, he held the position of Professor II at Rutgers.
Work on linear programming
Ellipsoid method
Khachiyan is best known for his four-page February 1979 paper that indicated how an
ellipsoid method
In mathematical optimization, the ellipsoid method is an iterative method for minimizing convex functions. When specialized to solving feasible linear optimization problems with rational data, the ellipsoid method is an algorithm which finds ...
for
linear programming
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is ...
can be implemented in polynomial time.
The paper was translated into several languages and spread around the world unusually fast. Authors of a 1981 survey of his work noted that it "has caused great excitement and stimulated a flood of technical papers" and was covered by major newspapers.
It was originally published without proofs, which were provided by Khachiyan in a later paper published in 1980 and by
Peter Gács and
Laszlo Lovász in 1981.
It was Gács and Lovász who first brought attention to Khachiyan's paper at the International Symposium on Mathematical Programming in Montreal in August 1979.
It was further popularized when
Gina Kolata reported it in ''
Science Magazine'' on November 2, 1979.
Khachiyan's theory is considered a groundbreaking one that "helped advance the field of linear programming."
Giorgio Ausiello noted that the method was not practical, "but it was a real breakthrough for the world of operations research and computer science, since it proved that the design of polynomial time algorithms for linear programming was possible and in fact opened the way to other, more practical, algorithms that were designed in the following years."
Personal life and death
Khachiyan spoke Russian and English, but not
Armenian.
Bahman Kalantari noted that "For some, his English accent wasn’t always easy to understand."
The 1979 ''
New York Times
''The New York Times'' (''the Times'', ''NYT'', or the Gray Lady) is a daily newspaper based in New York City with a worldwide readership reported in 2020 to comprise a declining 840,000 paid print subscribers, and a growing 6 million paid ...
'' profile of him described Khachiyan as "a relaxed, friendly young man in a sweater who speaks a little English, which he learned in high school."
He was known as "Leo"
and "Lenya" to his friends and colleagues.
Václav Chvátal
Václav (Vašek) Chvátal () is a Professor Emeritus in the Department of Computer Science and Software Engineering at Concordia University in Montreal, Quebec, Canada and a Visiting Professor at Charles University in Prague. He has published ext ...
described him as "selfless, open, patient, sympathetic, understanding, considerate."
Michael Todd, another colleague, described him as "cynical about politics," "very modest and kind to his friends," and "intolerant of condescension and pomposity."
Khachiyan married Olga Pischikova Reynberg, of
Russian-Jewish
The history of the Jews in Russia and areas historically connected with it goes back at least 1,500 years. Jews in Russia have historically constituted a large religious and ethnic diaspora; the Russian Empire at one time hosted the largest pop ...
origin, in 1985.
They had two daughters,
Anna
Anna may refer to:
People Surname and given name
* Anna (name)
Mononym
* Anna the Prophetess, in the Gospel of Luke
* Anna (wife of Artabasdos) (fl. 715–773)
* Anna (daughter of Boris I) (9th–10th century)
* Anna (Anisia) (fl. 1218 to 1221) ...
and Nina,
who were teenagers at the time of his death.
He became a
naturalized
Naturalization (or naturalisation) is the legal act or process by which a non-citizen of a country may acquire citizenship or nationality of that country. It may be done automatically by a statute, i.e., without any effort on the part of the in ...
U.S. citizen in 2000.
He died of a
heart attack
A myocardial infarction (MI), commonly known as a heart attack, occurs when blood flow decreases or stops to the coronary artery of the heart, causing damage to the heart muscle. The most common symptom is chest pain or discomfort which ma ...
in
South Brunswick, New Jersey
South Brunswick is a township in Middlesex County, New Jersey, United States. The township is centrally located within the Raritan Valley region and is an outer-ring suburb of New York City in the New York metropolitan area. As of th2020 ...
on April 29, 2005, at the age of 52.
Recognition
In 1982 he was awarded the prestigious
Fulkerson Prize
The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of $1,500 each are presented at e ...
by the
Mathematical Programming Society The Mathematical Optimization Society (MOS), known as the Mathematical Programming Society until 2010,American Mathematical Society
The American Mathematical Society (AMS) is an association of professional mathematicians dedicated to the interests of mathematical research and scholarship, and serves the national and international community through its publications, meeting ...
for outstanding papers in the area of discrete mathematics,
particularly his 1979 article "A polynomial algorithm in linear programming."
Khachiyan was considered a "noted expert in computer science whose work helped computers process extremely complex problems."
He was called one of the world's most famous computer scientists at the time of his death by Haym Hirsh, chair of the computer science department at Rutgers.
"Computer scientists and mathematicians say his work helped revolutionize his field," noted his ''
New York Times
''The New York Times'' (''the Times'', ''NYT'', or the Gray Lady) is a daily newspaper based in New York City with a worldwide readership reported in 2020 to comprise a declining 840,000 paid print subscribers, and a growing 6 million paid ...
'' obituary.
Bahman Kalantari, a friend and colleague at Rutgers, wrote: "Surely, Khachiyan shall always remain to be among the greatest and most legendary figures in the field of mathematical programming."
References
;Notes
;Citations
External links
*
DBLP
DBLP is a computer science bibliography website. Starting in 1993 at Universität Trier in Germany, it grew from a small collection of HTML files and became an organization hosting a database and logic programming bibliography site. Since Novem ...
Leonid Khachiyan
In Memoriam: Leonid Khachiyanfrom the Computer Science Department, Rutgers University.
* SIAM news
Leonid Khachiyan, 1952–2005: An Appreciation
* Discrete Applied Mathematics
Remembering Leo Khachiyan* The
Mathematics Genealogy Project
The Mathematics Genealogy Project (MGP) is a web-based database for the academic genealogy of mathematicians.. By 31 December 2021, it contained information on 274,575 mathematical scientists who contributed to research-level mathematics. For a ty ...
Leonid Khachiyan
* New York Times
{{DEFAULTSORT:Khachiyan, Leonid
1952 births
2005 deaths
20th-century American mathematicians
21st-century American mathematicians
American people of Armenian descent
American computer scientists
Cornell University faculty
Moscow Institute of Physics and Technology alumni
Moscow Institute of Physics and Technology faculty
Mathematicians from Moscow
Russian people of Armenian descent
Soviet Armenians
Soviet mathematicians
Rutgers University faculty
Soviet computer scientists
Soviet emigrants to the United States
Naturalized citizens of the United States