Loading article…
ジャック・エドモンズ | |
|---|---|
 カナダのオンタリオ州にある自宅の外にある国立公園の岩とエドモンズ | |
| 生まれる | ジョン・ロバート・エドモンズ 1934年4月5日 ワシントン D.C.、米国 |
| 母校 | |
| 知られている | |
| 受賞歴 | ジョン・フォン・ノイマン理論賞(1985) |
| 科学者としてのキャリア | |
| フィールド | コンピュータサイエンス、数学 |
| 機関 | |
| 博士課程の学生 | |
ジャック・R・エドモンズ（1934年4月5日生まれ）は、アメリカ生まれのコンピューター科学者、数学者であり、生涯の大半をカナダで暮らし、働いてきました。エドモンズは、組合せ最適化、多面体組合せ論、離散数学、コンピューティング理論の分野に根本的な貢献をしました。エドモンズは、1985年にジョン・フォン・ノイマン理論賞を受賞しました。
初期のキャリア
エドモンズはマッキンリー技術高校に通い、1952年に卒業した。[1]彼はこの学校が自身のキャリアに与えた影響について語っている（例えば2014年のNISTギャラリー入会時[2] [3] [4]）。エドモンズはデューク大学に通い、その後1957年にジョージ・ワシントン大学で学士号を取得した。その後1960年にメリーランド大学でブルース・L・ラインハートの指導の下、グラフを曲面に埋め込む問題についての論文で修士号を取得した。[5] [6] 1959年から1969年まで国立標準技術研究所（当時は国立標準局）に勤務し、 1961年にアラン・ゴールドマンが新設したオペレーションズ・リサーチ部門の創設メンバーとなった。ゴールドマンは、エドモンズがランド研究所がスポンサーとなってカリフォルニア州サンタモニカで行ったワークショップに参加できるようにしたことで、エドモンズに極めて重要な影響を与えた。ここでエドモンズは、より効率的に実行できるアルゴリズムのクラスを定義するという発見を初めて発表しました。この時期、ほとんどの組合せ論の学者はアルゴリズムに注目していませんでした。しかし、エドモンズはアルゴリズムに惹かれ、これらの初期の研究は、その後のマトロイドと最適化に関する研究の重要な発展となりました。彼は 1961 年から 1965 年まで NP 対 P というテーマに取り組み、1966 年に NP ≠ P および NP ∩ coNP = P という仮説を提唱しました。
研究
エドモンズの 1965 年の論文「Paths, Trees and Flowers」は、効率的な組み合わせアルゴリズムの数学的理論を確立する可能性を初めて示唆した傑出した論文でした。彼の初期の注目すべき貢献の 1 つは、グラフ上で最大マッチングを構成するためのブロッサム アルゴリズムで、1961 年に発見され[7]、1965 年に発表されました[8]。これは、グラフの最大マッチングに対する最初の多項式時間アルゴリズムでした。重み付きグラフへの一般化[9]は、組み合わせ最適化における線形計画法の考え方の使用における概念的なブレークスルーでした。これは、インスタンスの答えが yes であることの証明、つまり「証人」が存在することと、インスタンスの答えが no であることの証明、つまり「証人」が存在することの重要性を確固たるものにしました。このブロッサム アルゴリズムの論文で、エドモンズは、実行可能な問題を多項式時間で解決できる問題として特徴付けています。これは、コブハム - エドモンズのテーゼの起源の 1 つです。[10]
コブハム・エドモンズのテーゼの画期的な点は、実用的なアルゴリズムと非実用的なアルゴリズム (現代の言葉で言えば、扱いやすい問題と扱いにくい問題)の違いを特徴付ける多項式時間の概念を定義したことです。今日では、多項式時間で解決できる問題は複雑性クラス PTIME、または単にPと呼ばれています。
エドモンズの論文「最大マッチングと 0-1 頂点の多面体」は、彼の以前の研究とともに、最大マッチングの構築のための驚くべき多項式時間アルゴリズムを示しました。最も注目すべきは、これらの論文が、組み合わせ最適化問題に関連する多面体の適切な特性評価が、線形計画法の双対理論を介して、その問題の解決のための効率的なアルゴリズムの構築にどのようにつながるかを示したことです。
エドモンズのもう一つの画期的な研究はマトロイドの分野です。彼はグラフのすべての全域木、より一般的にはマトロイドのすべての独立集合の多面体記述を発見しました。 [11]これを基に、離散数学への線型計画法の新しい応用として、彼はマトロイド交差定理を証明しました。これは非常に一般的な組合せ論的最小最大定理であり[12] [13]、現代の言葉で言えば、マトロイド交差問題がNPとco-NPの両方に存在することを示しています。エドモンズは、最大重み分岐アルゴリズム[14]と辺素分岐のパッキング[15]に関する定理と、リチャード・カープとのより高速なフローアルゴリズムに関する研究でよく知られています。エドモンズ-ガライ分解定理は、マッチングの観点から有限グラフを記述します。彼はポリマトロイド[12] 、リチャード・ジャイルズとの共著によるサブモジュラーフロー[16]、ハイパーグラフの研究におけるクラッターとブロッカーという用語を導入した。[7]彼の研究[17]で繰り返し取り上げられるテーマは、時間計算量が入力サイズとビット計算量によって多項式的に制限されるアルゴリズムを探すことである。[7]
キャリア
1969年以降、1991年から1993年を除いて、ウォータールー大学数学部の組合せ論および最適化学科の教授を務め、組合せ最適化問題とそれに関連する多面体を研究対象とした。この間、12名の学生の博士課程を指導した。デューク大学、ジョージ・ワシントン大学、メリーランド大学、スタンフォード大学、プリンストン大学、コーネル大学のほか、中国、ルーベン（ベルギー）、コペンハーゲン、デンマーク南部（オーデンセ）、パリ、マルセイユ、グルノーブル（フランス）、ボン、ケルン（ドイツ）の大学で講義を行ったり、研究休暇を取ったりした。
1991年から1993年にかけて、彼はウォータールー大学との紛争（「エドモンズ事件」）に巻き込まれた。[18] [19]大学側は提出された手紙が辞職書に相当すると主張したが、エドモンズはそれを否定した。[20]この紛争は1993年に解決し、彼は大学に戻った。
エドモンズは1999年にウォータールー大学を退職した。
受賞と栄誉
エドモンズは1985年にジョン・フォン・ノイマン理論賞を受賞した。
2001年、彼の論文「道、木、花」は、国立標準技術研究所の「計測標準と技術における1世紀の卓越性」記念版で 優れた出版物として表彰されました。
彼は2002年にオペレーションズ・リサーチ・マネジメント科学研究所のフェローに選出された。[21]
2006年、デンマーク女王はエドモンズに南デンマーク大学の名誉博士号を授与した。
2014 年に彼は著名な科学者として表彰され、国立標準技術研究所のギャラリーに加わりました。
2001年に開催された第5回オーソワ組合せ最適化ワークショップは彼に捧げられた。[13]
私生活
ジャックの息子ジェフ・エドモンズはヨーク大学のコンピューターサイエンスの教授であり、妻のキャシー・キャメロンはローリエ大学の数学の教授である。
参照
参考文献
- ^ "Tech_alumni_pp48" より。
- ^ 「NIST 著名な科学者、エンジニア、管理者のギャラリー: ギャラリーに 9 つのポートレートを追加」(PDF)。2014 年 10 月 10 日。
- ^ 「巡回セールスマン問題と P 対 NP: 1960 年代の NIST における数学アルゴリズムの複雑性に関する理論的研究」。
- ^ エドモンズ、ジャック（2014年10月10日）。「巡回セールスマン問題とP対NP：1960年代のNISTにおける数学アルゴリズムの複雑性に関する理論的研究」（PDF）。
- ^ 「ジャック・エドモンズ」。数学系譜プロジェクト。 2022年6月23日閲覧。
- ^ Edmonds Jr., John Robert (1960). 有向多面体表面の組み合わせ表現。hdl :1903/24820。2022年6月23日閲覧。
- ^ abc エドモンズ、ジャック (1991)、「天国の一瞥」、JK Lenstra ; AHGリンノイ・カン; A. Schrijver (編)、「数学的プログラミングの歴史 – 個人的な思い出のコレクション」、CWI、アムステルダムおよび北オランダ、アムステルダム、32–54 ページ
- ^ エドモンズ、ジャック (1965)。「小道、木、花」。Can . J. Math . 17 :449–467. doi : 10.4153/CJM-1965-045-4 . S2CID 247198603。
- ^エドモンズ、ジャック (1965)。「最大マッチングと 0,1 頂点を 持つ多面体」。国立標準局セクション B 研究ジャーナル。69 (1 および 2): 125–130。doi : 10.6028/ jres.069B.013。
- ^ ジェラール・ムーラン (2014).アルゴリズムと複雑さ。エルゼビア。 p. p. 4.ISBN 978-0-08093391-7
問題は、
多項式時間で解くことができる場合、実行可能で
あると言われる（エドモンズ[26] [1965, Paths, trees, and flowers]で初めて述べられた）。
- ^エドモンズ、ジャック (1971) 。「マトロイドと貪欲アルゴリズム」。数学プログラミング (プリンストンシンポジウム数学プログラム 1967)。1 : 127–136。
- ^ ab Edmonds, Jack (1970)。「サブモジュラー関数、マトロイド、および特定の多面体」。R. Guy、H. Hanam、N. Sauer、J. Schonheim (編)。組み合わせ構造とその応用 (Proc. 1969 Calgary Conference)。Gordon and Breach、ニューヨーク。pp. 69–87。。
- ^ ab Jünger, Michael; Reinelt, Gerhard; Rinaldi, Giovanni 編 (2003)、組み合わせ最適化 - ユーレカ、あなたは縮みます!、Lecture Notes in Computer Science、vol. 2570、Springer
- ^ エドモンズ、ジャック (1967)。「最適分岐」。国立標準局セクションBの研究ジャーナル。71B (4): 233–240。doi : 10.6028/ jres.071B.032。
- ^ エドモンズ、ジャック (1973)、R. ラスティン (編)、「エッジ分離分岐」、組み合わせアルゴリズム | クーラント コンピュータ サイエンス シンポジウム 9、1972、カリフォルニア州モントレー、1972: Algorithmics Press、ニューヨーク: 91–96
{{citation}}: CS1 メンテナンス: 場所 (リンク) - ^ エドモンズ、ジャック; ジャイルズ、リチャード (1977)、PL ハンマー; EL ジョンソン; BH コルテ; GL ネムハウザー (編)、「グラフ上のサブモジュラー関数の最小最大関係」、整数計画法の研究 | 整数計画法に関するワークショップ議事録、ボン、1975、離散数学の年報、1、北ホラント、アムステルダム: 185–204、doi :10.1016/S0167-5060(08)70734-9、ISBN 9780720407655
- ^ Christoph Witzgall (2001)、「Paths, Trees, and Flowers」、A Century of Excellence in Measurements, Standards, and Technology (PDF) 、国立標準技術研究所、pp. 140–144、2006-03-25にオリジナル(PDF)からアーカイブ、2011-08-11 に取得
- ^ UW Gazette、1992年10月7日: CAUTがジャック・エドモンズ事件に介入
- ^ 編集者による序文 アーカイブ 2010-10-27 at the Wayback Machine、Kenneth Westhues 編著『Workplace Mobbing in Academe: Reports from Twenty Universities』、ルイストン、NY: The Edwin Mellen Press、2004
- ^ ウォータールー大学デイリー・ブレティン、2001年3月5日：会議でジャック・エドモンズ氏を表彰
- ^ フェロー：アルファベット順リスト、オペレーションズ・リサーチ・アンド・マネジメント・サイエンス研究所、2019年5月10日時点のオリジナルよりアーカイブ、 2019年10月9日取得
外部リンク
- 数学系譜プロジェクトのジャック・エドモンズ
- オペレーションズ・リサーチおよび経営科学研究所のジャック・エドモンズの経歴