イェフィム・ディニッツ

イェフィム・ディニッツ（ロシア語：Ефим Абрамович Диниц、^[2] ヘブライ語：יפים דיניץ）は、ソ連およびイスラエルの コンピュータ科学者であり、モスクワ学派の多項式時間アルゴリズムに関係している。^[3]彼は最大フローを計算するためのディニッチのアルゴリズムを発明し、 ^[4]ブール行列またはmod 2行列を乗算する4 人のロシア人のアルゴリズムの発明者の 1 人であった。^{[5] : 243, 250}

ディニッツはモスクワ国立大学のゲオルギー・アデルソン＝ヴェルスキーのグループで修士号を取得した。 ^{[4] [6] [3]} 1969年、アデルソン＝ヴェルスキーはアルゴリズムに関するセミナーを開始した。後に彼の学生や彼の側近たちはこれを「モスクワにおける多項式時間アルゴリズムの科学的活動の中心」と形容した。^[3]ディニッツによると、 1969年のディニッツのアルゴリズムの開発につながったのは「アデルソン＝ヴェルスキーのアルゴリズムの授業」での演習だった。 ^[4]振り返ってみると、ディニッツと彼のクラスメートは、アルゴリズムの設計はアデルソン＝ヴェルスキーのグループの雰囲気を反映していたと書いている。^[3]ディニッツは次のように述べている。^[4]

私たちアデルソン＝ヴェルスキーの学生は、彼の講義からソビエトコンピューティングスクールのパラダイム全体を吸収しました。このパラダイムは、問題の徹底的な調査と、必要なコンポーネントとしてのスマートなデータ構造の維持および償却実行時間分析の使用に基づいて、経済的なアルゴリズムを開発しようとする熱意で構成されていました。…したがって、1969 年 1 月に発明された私のネットワークフローアルゴリズムが、階層化されたネットワークデータ構造を使用および維持し、実行時間の繊細な償却分析を採用することで、フォード＆ファルカーソンアルゴリズムを改良したことは驚くべきことではありませんでした。

ディニッツは1970年にこのアルゴリズムを発表した。^{[7] [8]}

1969年初頭、ディニッツはクラスメートのミハイル・クロンロッドとともに割り当て問題に取り組んでおり、「より高速な割り当てアルゴリズムの探索が本格的に始まった」一連の研究に貢献した。^{[9] [4] [10]ディニッツとクロンロッドがその年の後半に発表したアルゴリズムは、} n^頂点グラフの割り当て問題をO ( n3 )ステップで解くことができた。^{[9] [11]}

アデルソン＝ヴェルスキーのアルゴリズムゼミに在籍中、ディニッツとクロンロッドは、ITEPの数学研究所で働く2人の若い数学者、ウラジミール・アルラザロフとイゴール・ファラジェフと出会った。 [ ^{12] [6] 1968年から1969年の}政治的事件まで、この研究所はアデルソン＝ヴェルスキーの学友で長年の協力者であるアレクサンドル・クロンロッドによって運営されていた。^{[6] [13]} 1970年、ディニッツ、ミハイル・クロンロッド、アルラザロフ、ファラジェフは、ブール行列乗算アルゴリズムを発表し、 「4人のロシア人」として有名になった。^{[14] [15]}

アデルソン＝ヴェルスキーは、1969年にアレクサンドル・クロンロッドをITEPから解雇することになった1968年の書簡にも署名していた。1970年、機械数学部はアデルソン＝ヴェルスキーの学生グループ全員を卒業し、アデルソン＝ヴェルスキーはモスクワ国立大学で教えることを禁じられた。^[6]しかし、ディニッツはフローアルゴリズムの研究を続けた。彼はモスクワ国立大学に商品フロー問題に関する博士論文を書き、1972年に提出した。^{[16] [17]彼は、ちょうど西側でそれを導入した}エドモンズとカープとは独立して容量スケーリングのアイデアを開発し、それを使って最小費用フロー問題に対する最初の多項式時間アルゴリズムの1つを発明した。^{[16] [3] [18]}

ディニッツはクラスメイトのアレクサンドル・カルザノフとも連絡を取り続け、1974年に彼と共同で最小費用フロー問題に関する論文を発表した。 ^{[6] [4] [10] [16]} 1975年、ディニッツとカルザノフはアデルソン＝ヴェルスキーとともにネットワークフローアルゴリズムに関する本を出版した。この本では「後に（場合によってはかなり後になって）西洋で独立して発見された多くの主要な結果について説明している」。^{[16] [10] [4]}

1974年、テクニオンのシモン・エヴェンと彼の大学院生アロン・イタイは、ディニッツの最大フローアルゴリズムと、カルザノフが同時期に発表したネットワークフローアルゴリズムに興味を持ちました。^[4]ディニッツのアルゴリズムの説明は、ジャーナルのページ数制限のため非常に圧縮されていましたが、カルザノフがディニッツの論文に暗黙的に含まれていた概念を明示的に説明したおかげで、エヴェンとイタイはアルゴリズムのほとんどを解読することができました。^[4]最後のギャップを独自の新しい手法で埋めた後、エヴェンとイタイはディニッツのアルゴリズムの実用的なバージョンを完成させ、エヴェンはそれを多くの西洋の大学での講演で公表しました。^[4]

ディニッツの名前は論文の英訳では「EA ディニック」と翻字されたため、エヴェンとイタイのバージョンのアルゴリズムは西洋ではディニックのアルゴリズムとして知られるようになり、その文脈では彼の名前は「[dinits] ではなく [dinik] と誤って表現された」。^[4]

1990年代、エヴェンはついにディニッツ本人からディニッツのアルゴリズムのオリジナル版を学ぶ機会を得た。^{[4] 1992年、ディニッツはエヴェンとテクニオンの他の2人のコンピュータ科学者とともに}バタフライネットワークに関する論文を発表し、所属をベングリオン大学と記載した。ディニッツは後に、エヴェンがテクニオンの准教授として採用されるよううまく戦ったことを回想していると伝えられている。^[19]彼は1994年に発表した論文で所属をテクニオンと記載し、1997年にはテクニオンの博士課程の学生を指導した。^{[20] [21]ディニッツは1998年に}ベングリオン大学のコンピュータサイエンス学部に加わり、2019年に学部は彼の退職祝いを行った。^[22]

1990年代後半から2000年代にかけてシュロモ・モラン、シュムエル・ザックスと共著した論文により、ディニッツのエルデシュ数は2である。^{[23] [24]}

• 「Yefim Dinitz」。ACMデジタル ライブラリ。