Jump to content

Yefim Dinitz

Add links
From Wikipedia, the free encyclopedia
Yefim Dinitz
Born
Yefim Abramovich Dinitz
Other namesE. A. Dinic
TitleEmeritus Full Professor[1]
Academic background
Academic advisorsGeorgy Adelson-Velsky
Shimon Even
Academic work
DisciplineComputer scientist
School or traditionMoscow school of polynomial-time algorithms
InstitutionsMoscow State University
Technion
Ben-Gurion University
Notable worksDinic's algorithm
Four Russians' Method
Websitehttps://www.cs.bgu.ac.il/~dinitz/

Yefim Dinitz (Russian: Ефим Абрамович Диниц,[2] Hebrew: יפים דיניץ) is a Soviet and Israeli computer scientist associated with the Moscow school of polynomial-time algorithms.[3] He invented Dinic's algorithm for computing maximal flow,[4] and he was one of the inventors of the Four Russians' algorithm for multiplying Boolean or mod 2 matrices.[5]: 243, 250 

Education and early work in the Adelson-Velsky group

[edit]

Dinitz studied for a master's degree in Georgy Adelson-Velsky's group at Moscow State University.[4][6][3] In 1969, Adelson-Velsky started a seminar on algorithms, which his students and others close to him would later describe as "the centre of scientific activity in polynomial-time algorithmics in Moscow".[3] It was an exercise in "Adel'son-Vel'sky's Algorithms class", according to Dinitz, that led to the development of Dinic's algorithm in 1969.[4] Looking back, Dinitz and his classmates would write that the design of the algorithm reflected the atmosphere of Adelson-Velsky's group.[3] In Dinitz's words:[4]

We, Adel'son-Vel'sky's students, absorbed the whole paradigm of the Soviet computing school from his lectures. This paradigm consisted of eagerness to develop economical algorithms based on the deep investigation of a problem and on the use of smart data structure maintenance and amortized running time analysis as necessary components. … Hence, it was not surprising that my network flow algorithm, invented in January 1969, improved the Ford&Fulkerson algorithm by using and maintaining a layered network data structure and employing a delicate amortized analysis of the running time.

Dinitz published the algorithm in 1970.[7][8]

In early 1969, Dinitz was also working on the assignment problem with his classmate Mikhail Kronrod, contributing to the body of work in which "the search for faster assignment algorithms began in earnest".[9][4][10] The algorithm Dinitz and Kronrod published later that year could solve the assignment problem for n-vertex graphs in O(n3) steps.[9][11][12]

During their time in Adelson-Velsky's algorithms seminar, Dinitz and Kronrod crossed paths with Vladimir Arlazarov and Igor Faradjev—two young mathematicians working in the Mathematical Laboratory at ITEP.[13][14][6] The lab was directed, until a political incident in 1968–1969, by Adelson-Velsky's academic sibling and longtime collaborator Aleksandr Kronrod.[6][15] In 1970, Dinitz, Mikhail Kronrod, Arlazarov, and Faradjev published the Boolean matrix multiplication algorithm that would make them famous as the "Four Russians".[16][17][18]

Work in Moscow after the Adelson-Velsky group

[edit]

Adelson-Velsky had also signed the 1968 letter that led to Aleksandr Kronrod's 1969 dismissal from ITEP. In 1970, the Faculty of Mechanics and Mathematics graduated Adelson-Velsky's whole student group, and Adelson-Velsky was banned from teaching at Moscow State University.[6] However, Dinitz kept working on flow algorithms. He wrote a Moscow State University Ph.D. thesis on commodity flow problems, which he submitted in 1972.[19][20] He developed the idea of capacity scaling independently of Edmonds and Karp, who had just introduced it in the West, and he used it to invent one of the first polynomial-time algorithms for the minimum-cost flow problem.[19][3][21]

Dinitz also stayed in touch with his classmate Aleksandr Karzanov, publishing a paper on the minimum-cost flow problem with him in 1974.[6][4][10][19][22] In 1975, Dinitz and Karzanov joined Adelson-Velsky in publishing a book on network flow algorithms, which "describe[d] many major results … that were independently discovered later (and in some cases much later) in the West".[19][23][10][4]

Publicity in the West

[edit]

In 1974, Shimon Even and his graduate student Alon Itai at the Technion got curious about Dinitz's maximal flow algorithm, as well as a network flow algorithm that Karzanov had published around the same time.[4] Dinitz's description of the algorithm was very compressed, due to journal page limits, but Even and Itai managed to decipher most of it, thanks in part to Karzanov's explicit explanation of a concept that was implicit in Dinitz's paper.[4] After filling the last gap with a new technique of their own, Even and Itai had a working version of Dinitz's algorithm, which Even publicized in talks at many Western universities.[4]

Dinitz's name was transliterated as "E. A. Dinic" in the English translation of his paper, so Even and Itai's version of his algorithm became known as Dinic's algorithm in the West, and his name was "rendered incorrectly as [dinik] instead of [dinits]" in that context.[4]

Later work at the Technion and Ben-Gurion University

[edit]

In the 1990s, Even finally got a chance to learn the original version of Dinitz's algorithm from Dinitz himself.[4] In 1992, Dinitz published a paper on the butterfly network with Even and two other Technion computer scientists, listing his affiliation as Ben-Gurion University. Dinitz would reportedly later recall that Even fought successfully for him to be hired as an associate professor at the Technion.[24] He listed his affiliation as the Technion on a paper published in 1994, and he advised a Technion Ph.D. student in 1997.[25][26] Dinitz joined the computer science department at Ben-Gurion University in 1998, and the department held a retirement celebration for him in 2019.[27]

Due to his publications with Shlomo Moran and Shmuel Zaks in the late 1990s and the 2000s, Dinitz has an Erdős number of two.[28][29]

References

[edit]
  1. ^ "Yefim Dinitz". Ben-Gurion University Research Portal. Retrieved 23 December 2023.
  2. ^ Диниц Ефим Абрамович [Dinitz Yefim Abramovich]. ИСТИНА ISTINA. Retrieved 23 December 2023.
  3. ^ a b c d e Arlazarov, V. L.; Dinitz, E. A.; Ilyashenko, Yu. S.; Karzanov, A. V.; Karpenko, S. M.; Kirillov, A. A.; Konstantinov, N. N.; Kronrod, M. A.; Kuznetsov, O. P.; Okun', L. B.; Pevzner, P. A.; Semenov, A. L.; Faradzhev, I. A.; Cherkasskii, B. V.; Khovanskii, A. G. (2014). "Georgy Maksimovich Adelson-Velsky (obituary)". Russian Mathematical Surveys. 69 (4): 743–751. Bibcode:2014RuMaS..69..743A. doi:10.1070/RM2014v069n04ABEH004909. S2CID 123048550.
  4. ^ a b c d e f g h i j k l Dinitz, Yefim (2006). "Dinitz' Algorithm: The Original Version and Even's Version". In Goldreich, Oded; Rosenberg, Arnold L.; Selman, Alan L. (eds.). Theoretical Computer Science: Essays in Memory of Shimon Even. Lecture Notes in Computer Science. Vol. 3895. Springer. pp. 218–240. doi:10.1007/11685654_10. ISBN 978-3-540-32880-3.
  5. ^ Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D. (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley. ISBN 978-0-201-00029-0. OCLC 1147299.
  6. ^ a b c d e Donskoy, Mikhail. История «Каиссы» [History of "Kaissa"]. Виртуальный Компьютерный Музей [Russian Virtual Computer Museum]. Retrieved 25 December 2023.
  7. ^ "An algorithm for the solution of the problem of maximal flow in a network with power estimation". Math-Net.Ru. Retrieved 24 December 2023.
  8. ^ E. A. Dinic (1970). "Algorithm for solution of a problem of maximum flow in a network with power estimation" (PDF). Doklady Akademii Nauk SSSR. 11: 1277–1280.
  9. ^ a b Duan, Ran; Pettie, Seth (1 January 2014). "Linear-Time Approximation for Maximum Weight Matching" (PDF). Journal of the ACM. 61: 1–23. doi:10.1145/2529989. S2CID 207208641.
  10. ^ a b c Shalyto, А. А. (12 April 2022). Сто лет со дня рождения Георгия Максимовича Адельсона-Вельского [A hundred years since the day of birth of Georgy Adelson-Velsky]. Виртуальный Компьютерный Музей [;Russian Virtual Computer Museum]. Retrieved 25 December 2023.
  11. ^ "An algorithm for solving the assignment problem". Math-Net.Ru. Retrieved 24 December 2023.
  12. ^ Dinitz, Y. A.; Kronrod, M. A. (1969). "An algorithm for solving the assignment problem". Doklady Akademii Nauk SSSR. 189 (1): 23–25.
  13. ^ Faradjev, Igor (1–7 July 2018). 'Symmetry vs Regularity'. How it started and what it led to. Symmetry vs Regularity: The first 50 years since Weisfeiler-Leman stabilization. Pilsen. Talk slides.
  14. ^ Faradjev, I. A. (2020). Симметрия и регулярность. Как это начиналось и к чему привело [Symmetry and regularity. How it started and what it led to]. Информационные Технологии И Вычислительные Системы (4): 71–77. doi:10.14357/20718632200406. S2CID 241168270.
  15. ^ Landis, E. M.; Yaglom, I. M. (2002). Gautschi, Walter (ed.). "Remembering A. S. Kronrod". Math. Intelligencer. 24 (1). Translated by Brudno, Viola: 22–30. doi:10.1007/BF03025307. S2CID 119452130. Archived from the original on 2006-07-21.
  16. ^ Chan, Timothy M. (2015). "Speeding up the Four Russians Algorithm by About One More Logarithmic Factor". Proceedings of the 2015 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics. pp. 212–217. doi:10.1137/1.9781611973730.16. ISBN 978-1-61197-374-7.
  17. ^ "On economical construction of the transitive closure of an oriented graph". Math-Net.Ru. Retrieved 24 December 2023.
  18. ^ Arlazarov, V. L.; Dinitz, Y. A.; Kronrod, M. A.; Faradžev, I. A. (1970). Об экономном построении транзитивного замыкания ориентированного графа [On economical construction of the transitive closure of a directed graph]. Doklady Akademii Nauk SSSR. 194 (11). Originally published as: Арлазаров, В. Л.; Диниц, Е. А.; Кронрод, М. А.; Фараджев, И. А. (1970). Об экономном построении транзитивного замыкания ориентированного графа. Доклады Академии Наук СССР. 134 (3).
  19. ^ a b c d Goldberg, Andrew V.; Gusfield, Dan (June 1991). "Потоковые Алгоритмы (Flow Algorithms) (G. M. Adel'son-Vel'ski, E. A. Dinits, and A. V. Karzanov)". SIAM Review. 33 (2): 306–314. doi:10.1137/1033075. Book review.
  20. ^ Диниц, E. A. (1972). Экономные Алгоритмы Решения Задач Транспортного Типа [Efficient Algorithms for Solving Transportation Problems] (PhD thesis) (in Russian).
  21. ^ Диниц, E. A. (1973). Метод Поразрядного Сокращения Неязок и Транспортные Задачи [The Method of Scaling and Transportation Problems]. In Fridman, A. A. (ed.). Исследования по Дискретной Математике [Studies in Discrete Mathematics]. Moscow: Наука [ Science ].
  22. ^ Диниц, E. A.; Карзанов, А. В. (1974). "Об Экспоненциалъной Сложсности Алгоритмов Решения Общей и Транспортной Задач Линейного Програмироеания" [On Exponential Complexity of Algorithms for the General and Transportation Linear Programming Problems]. Труды XIX Конференций Молодых Ученых ИАТ. Moscow.
  23. ^ Адельсон-Вельский, Г. М.; Диниц, E. A.; Карзанов, А. В. (1975). Потоковые алгоритмы [Network flow algorithms]. Moscow: Наука [ Science ].
  24. ^ Goldreich, Oded (November 2003). Yefim Dinitz talk at Shimon Even's Party. A transcript of Dinitz's speech at Shimon Even's retirement party.
  25. ^ Dinitz, Yefim; Vainshtein, Alek (23 May 1994). "The connectivity carcass of a vertex subset in a graph and its incremental maintenance". Proceedings of the twenty-sixth annual ACM symposium on Theory of Computing. ACM. doi:10.1145/195058.195442. ISBN 978-0-89791-663-9.
  26. ^ "PhD and MSc Theses". Technion. Retrieved 27 December 2023.
  27. ^ ברכות לפרופ' יפים דיניץ על פרישתו לגמלאות. Ben-Gurion University. 14 January 2020. Archived from the original on 15 August 2021.
  28. ^ Grossman, Jerry (7 August 2020). "Erdos2". 2020.
  29. ^ "Dinitz, Yefim". zbMATH Open.
[edit]
Retrieved from "https://en.wikipedia.org/w/index.php?title=Yefim_Dinitz&oldid=1255264145"