Yefim Dinitz
{{Infobox academic
| name=Yefim Dinitz
| birth_name=Yefim Abramovich Dinitz
| other_names=E. A. Dinic
| title=Emeritus Full Professor
| website=https://www.cs.bgu.ac.il/~dinitz/
| education=
| school_tradition=Moscow school of polynomial-time algorithms
| academic_advisors=Georgy Adelson-Velsky
Shimon Even
| discipline=Computer scientist
| workplaces=Moscow State University
Technion
Ben-Gurion University
| notable_works=Dinic's algorithm
Four Russians' Method
}}
Yefim Dinitz ({{langx|ru|Ефим Абрамович Диниц}},{{r|dinitz profile istina}} {{langx|he|יפים דיניץ}}) is a Soviet and Israeli computer scientist associated with the Moscow school of polynomial-time algorithms.{{r|adelson-velsky obit}} He invented Dinic's algorithm for computing maximal flow,{{r|even's version}} and he was one of the inventors of the Four Russians' algorithm for multiplying Boolean or mod 2 matrices.{{r|alg design & analysis|pages=243, 250}}
Education and early work in the Adelson-Velsky group
Dinitz studied for a master's degree in Georgy Adelson-Velsky's group at Moscow State University.{{r|even's version|history of kaissa|adelson-velsky obit}} 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".{{r|adelson-velsky obit}} 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.{{r|even's version}} Looking back, Dinitz and his classmates would write that the design of the algorithm reflected the atmosphere of Adelson-Velsky's group.{{r|adelson-velsky obit}} In Dinitz's words:{{r|even's version}}
{{blockquote
| text=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.{{r|max flow profile mathnet|max flow}}
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".{{r|lin appx max wt|even's version|adelson-velsky centennial}} The algorithm Dinitz and Kronrod published later that year could solve the assignment problem for {{math|n}}-vertex graphs in {{math|O(n3)}} steps.{{r|lin appx max wt|assign prob}}
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.{{r|symmetry vs regularity paper|history of kaissa}} The lab was directed, until a political incident in 1968–1969, by Adelson-Velsky's academic sibling and longtime collaborator Aleksandr Kronrod.{{r|history of kaissa|a s kronrod memorial}} In 1970, Dinitz, Mikhail Kronrod, Arlazarov, and Faradjev published the Boolean matrix multiplication algorithm that would make them famous as the "Four Russians".{{r|one more log factor|econ construct profile mathnet}}
Work in Moscow after the Adelson-Velsky group
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.{{r|history of kaissa}} 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.{{r|flow algs rev|efficient transport}} 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.{{r|flow algs rev|adelson-velsky obit|scaling transport}}
Dinitz also stayed in touch with his classmate Aleksandr Karzanov, publishing a paper on the minimum-cost flow problem with him in 1974.{{r|history of kaissa|even's version|adelson-velsky centennial|flow algs rev}} 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".{{r|flow algs rev|adelson-velsky centennial|even's version}}
Publicity in the West
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.{{r|even's version}} 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.{{r|even's version}} 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.{{r|even's version}}
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.{{r|even's version}}
Later work at the Technion and Ben-Gurion University
In the 1990s, Even finally got a chance to learn the original version of Dinitz's algorithm from Dinitz himself.{{r|even's version}} 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.{{r|even's party}} He listed his affiliation as the Technion on a paper published in 1994, and he advised a Technion Ph.D. student in 1997.{{r|connect carcass|dinitz theses}} Dinitz joined the computer science department at Ben-Gurion University in 1998, and the department held a retirement celebration for him in 2019.{{r|dinitz retirement}}
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.{{r|erdos2|dinitz profile zbmath}}
References
{{reflist | refs=
| script-title=ru:Диниц Ефим Абрамович
| trans-title=Dinitz Yefim Abramovich
| url=https://istina.msu.ru/workers/40274820/
| access-date=23 December 2023
}}
| title=Yefim Dinitz
| website=Ben-Gurion University Research Portal
| url=https://cris.bgu.ac.il/en/persons/yefim-dinitz/ | access-date=23 December 2023
}}
| title=Dinitz, Yefim
| website=zbMATH Open
| url=https://zbmath.org/authors/dinitz.yefim
}}
| first1=Alfred V. | last1=Aho | author-link1=Alfred Aho
| first2=John E. | last2=Hopcroft | author-link2=John Hopcroft
| first3=Jeffrey D. | last3=Ullman | author-link3=Jeffrey Ullman
| title=The Design and Analysis of Computer Algorithms
| year=1974
| publisher=Addison-Wesley
| isbn=978-0-201-00029-0
| oclc=1147299
}}
| first=Yefim | last=Dinitz | author-link=Yefim Dinitz
| chapter=Dinitz' Algorithm: The Original Version and Even's Version
| pages=218–240
| chapter-url=https://link.springer.com/chapter/10.1007/11685654_10
| doi=10.1007/11685654_10
| editor-first1=Oded | editor-last1=Goldreich | editor-link1=Oded Goldreich
| editor-first2=Arnold L. | editor-last2=Rosenberg | editor-link2=Arnold L. Rosenberg
| editor-first3=Alan L. | editor-last3=Selman | editor-link3=Alan Selman
| title=Theoretical Computer Science: Essays in Memory of Shimon Even
| series=Lecture Notes in Computer Science | year=2006
| volume=3895 | publisher=Springer
| isbn=978-3-540-32880-3
}}
| title=Yefim Dinitz talk at Shimon Even's Party
| first=Oded | last=Goldreich | author-link=Oded Goldreich
| date=November 2003
| url=https://www.wisdom.weizmann.ac.il/~oded/even-dini.html
}} A transcript of Dinitz's speech at Shimon Even's retirement party.
| first1=V. L. | last1=Arlazarov
| first2=E. A. | last2=Dinitz
| first3=Yu. S. | last3=Ilyashenko | author-link3=Yulij Ilyashenko
| first4=A. V. | last4=Karzanov
| first5=S. M. | last5=Karpenko
| first6=A. A. | last6=Kirillov | author-link6=Alexandre Kirillov
| first7=N. N. | last7=Konstantinov | author-link7=Nikolay Konstantinov
| first8=M. A. | last8=Kronrod
| first9=O. P. | last9=Kuznetsov
| first10=L. B. | last10=Okun' | author-link10=Lev Okun
| first11=P. A. | last11=Pevzner | author-link11=Pavel A. Pevzner
| first12=A. L. | last12=Semenov | author-link12=Alexei Semenov (mathematician)
| first13=I. A. | last13=Faradzhev
| first14=B. V. | last14=Cherkasskii
| first15=A. G. | last15=Khovanskii | author-link15=Askold Khovanskii
| title=Georgy Maksimovich Adelson-Velsky (obituary)
| journal=Russian Mathematical Surveys
| date=2014
| volume=69 | number=4 | pages=743–751
| doi=10.1070/RM2014v069n04ABEH004909
| bibcode=2014RuMaS..69..743A
| s2cid=123048550
}}
| first1=Ran | last1=Duan
| first2=Seth | last2=Pettie
| date=1 January 2014
| title=Linear-Time Approximation for Maximum Weight Matching
| url=https://web.eecs.umich.edu/~pettie/papers/ApproxMWM-JACM.pdf
| journal=Journal of the ACM
| volume=61 | pages=1–23
| language=EN
| doi=10.1145/2529989 | s2cid=207208641
}}
| first=Timothy M. | last=Chan | author-link=Timothy M. Chan
| title=Speeding up the Four Russians Algorithm by About One More Logarithmic Factor
| doi=10.1137/1.9781611973730.16
| book-title=Proceedings of the 2015 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
| year=2015 | pages=212–217
| publisher=Society for Industrial and Applied Mathematics
| isbn=978-1-61197-374-7
}}
| first1=Y. A. | last1=Dinitz | author-link=Yefim Dinitz
| first2=M. A. | last2=Kronrod
| title=An algorithm for solving the assignment problem
| journal=Doklady Akademii Nauk SSSR
| year=1969 | volume=189 | number=1 | pages=23–25
}}
| first=А. А. | last=Shalyto | author-link=Anatoly Shalyto
| script-title=ru:Сто лет со дня рождения Георгия Максимовича Адельсона-Вельского
| trans-title=A hundred years since the day of birth of Georgy Adelson-Velsky
| website=Виртуальный Компьютерный Музей [;Russian Virtual Computer Museum]
| date=12 April 2022
| url=https://www.computer-museum.ru/articles/yubilei/5017/
| access-date=25 December 2023
}}
| first=I. A. | last=Faradjev
| script-title=ru:Симметрия и регулярность. Как это начиналось и к чему привело
| trans-title=Symmetry and regularity. How it started and what it led to
| journal= Информационные Технологии И Вычислительные Системы
| year=2020 | number=4 | pages=71–77
| doi=10.14357/20718632200406
| s2cid=241168270
| url=https://www.mathnet.ru/rus/itvs429
}}
| first=Mikhail | last=Donskoy | author-link=Mikhail Donskoy
| script-title=ru:История «Каиссы»
| trans-title=History of "Kaissa"
| website=Виртуальный Компьютерный Музей [Russian Virtual Computer Museum]
| url=https://www.computer-museum.ru/games/kaissa1.htm
| access-date=25 December 2023
}}
| first1=E. M. | last1=Landis | author-link1=Evgenii Landis
| first2=I. M. | last2=Yaglom | author-link2=Isaak Yaglom
| translator-first=Viola | translator-last=Brudno
| editor-first=Walter | editor-last=Gautschi
| title=Remembering A. S. Kronrod
| journal=Math. Intelligencer
| year=2002 | volume=24 | issue=1 | pages=22–30
| doi=10.1007/BF03025307 | s2cid=119452130
| url=https://link.springer.com/article/10.1007/BF03025307
| url-status=live
| archive-url=https://web.archive.org/web/20060721211026/http://dip.sun.ac.za/~laurie/sccm00-01.ps.gz
| archive-date=2006-07-21
}}
| author=E. A. Dinic | author-link=Yefim Dinitz
| title=Algorithm for solution of a problem of maximum flow in a network with power estimation
| journal=Doklady Akademii Nauk SSSR
| year=1970 | volume=11 | pages=1277–1280
| url=http://www.cs.bgu.ac.il/~dinitz/D70.pdf
}}
| title=An algorithm for the solution of the problem of maximal flow in a network with power estimation
| website=Math-Net.Ru
| url=https://www.mathnet.ru/eng/dan35701
| access-date=24 December 2023
}}
| title=On economical construction of the transitive closure of an oriented graph
| website=Math-Net.Ru
| url=https://www.mathnet.ru/eng/dan35675
| access-date=24 December 2023
}}
| first=E. A. | last=Диниц | author-link=Yefim Dinitz
| script-title=ru:Экономные Алгоритмы Решения Задач Транспортного Типа
| trans-title=Efficient Algorithms for Solving Transportation Problems
| date=1972
| degree=PhD
| language=ru
| url=http://www.library.univ.kiev.ua/ukr/elcat/new/detail.php3?doc_id=823420
}}
| first=E. A. | last=Диниц | author-link=Yefim Dinitz
| script-chapter=ru:Метод Поразрядного Сокращения Неязок и Транспортные Задачи
| trans-chapter=The Method of Scaling and Transportation Problems
| editor-first=A. A. | editor-last=Fridman
| script-title=ru:Исследования по Дискретной Математике
| trans-title=Studies in Discrete Mathematics
| publisher=Наука [ Science ]
| place=Moscow
| year=1973
| url=https://search.rsl.ru/ru/record/01007131690
}}
| first1=Andrew V. | last1=Goldberg
| first2=Dan | last2=Gusfield
| title=Потоковые Алгоритмы (Flow Algorithms) (G. M. Adel'son-Vel'ski, E. A. Dinits, and A. V. Karzanov)
| journal=SIAM Review
| volume=33
| number=2
| pages=306–314
| date=June 1991
| doi=10.1137/1033075
| url=https://epubs.siam.org/doi/10.1137/1033075
}} Book review.
| first1=Yefim | last1=Dinitz | author-link1=Yefim Dinitz
| first2=Alek | last2=Vainshtein
| title=The connectivity carcass of a vertex subset in a graph and its incremental maintenance
| date=23 May 1994
| doi=10.1145/195058.195442
| url=https://dl.acm.org/doi/10.1145/195058.195442
| book-title=Proceedings of the twenty-sixth annual ACM symposium on Theory of Computing
| isbn=978-0-89791-663-9
| publisher=ACM
}}
| title=PhD and MSc Theses
| publisher=Technion
| url=https://graduate.technion.ac.il/advisor-20157/
| access-date=27 December 2023}}
| script-title=he:ברכות לפרופ' יפים דיניץ על פרישתו לגמלאות
| publisher=Ben-Gurion University
| date=14 January 2020
| url=http://in.bgu.ac.il/teva/cs/pages/news/test11.aspx
| url-status=dead
| archive-url=https://web.archive.org/web/20210815102858/http://in.bgu.ac.il/teva/cs/pages/news/test11.aspx
| archive-date=15 August 2021
}}
| first=Jerry | last=Grossman
| title=Erdos2 | version=2020 | date=7 August 2020
| url=https://sites.google.com/oakland.edu/grossman/home/the-erdoes-number-project/the-erdoes-number-project-data-files/erdos2
}}
}}
External links
- {{cite web
| title=Yefim Dinitz
| website=ACM Digital Library
| url=https://dl.acm.org/profile/81100307492
}}
{{DEFAULTSORT:Dinitz, Yefim}}
Category:Soviet computer scientists
Category:Israeli computer scientists