Leonid Khachiyan
Encyclopedia
Leonid Genrikhovich Khachiyan was a Soviet mathematician
of Armenia
n descent who taught Computer Science at Rutgers University
. He was most famous for his Ellipsoid algorithm
for linear programming
, which was the first such algorithm
known to have a polynomial running time. Even though this algorithm was shown to be impractical due to the high degree
of the polynomial in its running time, it has inspired other randomized algorithm
s for convex programming and is considered a significant theoretical breakthrough.
Khachiyan was born in St. Petersburg and moved to Moscow
with his parents at age 9. There he later earned a Ph.D.
in computational mathematics
in 1978 and a D.Sc. in computer science in 1984, both from the Computing Center of the USSR Academy of Sciences. In 1982 he won the prestigious Fulkerson Prize
from the Mathematical Programming Society
and the American Mathematical Society
for outstanding papers in the area of discrete mathematics
.
Prior to moving to the United States
in 1989, Khachiyan held a series of research and teaching positions at the Computing Center of the USSR Academy of Sciences and the Moscow Institute of Physics and Technology. In 1989 he joined Cornell University
’s School of Operations Research and Industrial Engineering as a visiting professor and had been at Rutgers since 1990.
After moving to the United States, Khachiyan's work continued some of its old ideas, as he worked on the complexity of maximal volume inscribed ellipsoids and wrote a paper on rounding polytope
s, adding some new ones. He wrote a series of papers with Bahman Kalantari on various matrix scaling and balancing problems
.
Khachiyan is survived by his wife of 20 years and two daughters who currently live in the United States. He is also survived by his father, a retired professor of theoretical mechanics, his mother, a retired civil engineer, and two brothers, all of whom live in Moscow.
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
of Armenia
Armenia
Armenia , officially the Republic of Armenia , is a landlocked mountainous country in the Caucasus region of Eurasia...
n descent who taught Computer Science at Rutgers University
Rutgers University
Rutgers, The State University of New Jersey , is the largest institution for higher education in New Jersey, United States. It was originally chartered as Queen's College in 1766. It is the eighth-oldest college in the United States and one of the nine Colonial colleges founded before the American...
. He was most famous for his Ellipsoid algorithm
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 an optimal solution in a finite number of steps.The...
for linear programming
Linear programming
Linear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...
, which was the first such algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
known to have a polynomial running time. Even though this algorithm was shown to be impractical due to the high degree
Degree (mathematics)
In mathematics, there are several meanings of degree depending on the subject.- Unit of angle :A degree , usually denoted by ° , is a measurement of a plane angle, representing 1⁄360 of a turn...
of the polynomial in its running time, it has inspired other randomized algorithm
Randomized algorithm
A randomized algorithm is an algorithm which employs a degree of randomness as part of its logic. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random bits...
s for convex programming and is considered a significant theoretical breakthrough.
Khachiyan was born in St. Petersburg and moved to Moscow
Moscow
Moscow is the capital, the most populous city, and the most populous federal subject of Russia. The city is a major political, economic, cultural, scientific, religious, financial, educational, and transportation centre of Russia and the continent...
with his parents at age 9. There he later earned a Ph.D.
Ph.D.
A Ph.D. is a Doctor of Philosophy, an academic degree.Ph.D. may also refer to:* Ph.D. , a 1980s British group*Piled Higher and Deeper, a web comic strip*PhD: Phantasy Degree, a Korean comic series* PhD Docbook renderer, an XML renderer...
in computational mathematics
Computational mathematics
Computational mathematics involves mathematical research in areas of science where computing plays a central and essential role, emphasizing algorithms, numerical methods, and symbolic methods. Computation in the research is prominent. Computational mathematics emerged as a distinct part of applied...
in 1978 and a D.Sc. in computer science in 1984, both from the Computing Center of the USSR Academy of Sciences. In 1982 he won the prestigious Fulkerson Prize
Fulkerson Prize
The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Programming Society and the American Mathematical Society . Up to three awards of $1500 each are presented at each International Symposium of the MPS...
from the Mathematical Programming Society
Mathematical Programming Society
Known as the Mathematical Programming Society until 2010, the Mathematical Optimization Society is an international association of researchers active in optimization...
and the American Mathematical Society
American Mathematical Society
The American Mathematical Society is an association of professional mathematicians dedicated to the interests of mathematical research and scholarship, which it does with various publications and conferences as well as annual monetary awards and prizes to mathematicians.The society is one of the...
for outstanding papers in the area of discrete mathematics
Discrete mathematics
Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous. In contrast to real numbers that have the property of varying "smoothly", the objects studied in discrete mathematics – such as integers, graphs, and statements in logic – do not...
.
Prior to moving to the United States
United States
The United States of America is a federal constitutional republic comprising fifty states and a federal district...
in 1989, Khachiyan held a series of research and teaching positions at the Computing Center of the USSR Academy of Sciences and the Moscow Institute of Physics and Technology. In 1989 he joined Cornell University
Cornell University
Cornell University is an Ivy League university located in Ithaca, New York, United States. It is a private land-grant university, receiving annual funding from the State of New York for certain educational missions...
’s School of Operations Research and Industrial Engineering as a visiting professor and had been at Rutgers since 1990.
After moving to the United States, Khachiyan's work continued some of its old ideas, as he worked on the complexity of maximal volume inscribed ellipsoids and wrote a paper on rounding polytope
Polytope
In elementary geometry, a polytope is a geometric object with flat sides, which exists in any general number of dimensions. A polygon is a polytope in two dimensions, a polyhedron in three dimensions, and so on in higher dimensions...
s, adding some new ones. He wrote a series of papers with Bahman Kalantari on various matrix scaling and balancing problems
Load balancing (computing)
Load balancing is a computer networking methodology to distribute workload across multiple computers or a computer cluster, network links, central processing units, disk drives, or other resources, to achieve optimal resource utilization, maximize throughput, minimize response time, and avoid...
.
Khachiyan is survived by his wife of 20 years and two daughters who currently live in the United States. He is also survived by his father, a retired professor of theoretical mechanics, his mother, a retired civil engineer, and two brothers, all of whom live in Moscow.
External links
- DBLPDBLPDBLP is a computer science bibliography website hosted at Universität Trier, in Germany. It was originally a database and logic programming bibliography site, and has existed at least since the 1980s. DBLP listed more than 1.3 million articles on computer science in January 2010...
: Leonid Khachiyan. - In Memoriam: Leonid Khachiyan from the Computer Science Department, Rutgers University.
- SIAM news: Leonid Khachiyan, 1952–2005: An Appreciation.
- The Mathematics Genealogy ProjectMathematics Genealogy ProjectThe Mathematics Genealogy Project is a web-based database for the academic genealogy of mathematicians. As of September, 2010, it contained information on approximately 145,000 mathematical scientists who contribute to "research-level mathematics"...
: Leonid Khachiyan. - New York Times : Obituary.