ユージン・ローラー

ユージン・レイトン（ジーン）・ローラー（1933年 - 1994年9月2日）は、アメリカのコンピュータ科学者であり、カリフォルニア大学バークレー校のコンピュータサイエンスの教授であった。^{[1] [2]}

ローラーは、フロリダ州立大学で3年間の数学の学部課程を修了した後、1954年に大学院生としてハーバード大学に入学した。1957年に修士号を取得し^[2]、学業を一時中断した。その間、法律学校に通い、米陸軍、研削砥石会社で働き^[3] 、 1959年から1961年にかけてはシルバニアで電気技師として働いた^{[2] 。 [4] 1958年にハーバード大学に戻り、1962年に}アンソニー・G・エッティンガーの指導の下、「離散数理計画法のいくつかの側面」と題する論文で応用数学の博士号を取得した^[1]。^{[2] [5]その後、}ミシガン大学の教員となり、1971年にバークレーに移った^[2] 。 1994年に死去する直前に退職した^{[6] 。}

バークレーでは、ローラーの博士課程の学生には、マーシャル・バーン、チップ・マーテル、アルヴィンド・ラグナサン、アーニー・ローゼンタール、フズール・サラン、デビッド・シュモイズ、タンディ・ワーノウなどがいた。^{[5] [7]}

ローラーは組合せ最適化の専門家であり、この分野の創始者でもあり、^[8]広く使われている教科書「組合せ最適化：ネットワークとマトロイド」の著者であり、「巡回セールスマン問題：組合せ最適化のガイドツアー」の共著者でもある。彼は、西洋で忘れ去られていた線形計画法の楕円体法を救う上で中心的な役割を果たした。 ^{[1] [9]また、彼は（DEウッドと共著で）1966年に}引用数の多い分岐限定法アルゴリズムの調査論文を執筆し、 ^{[10] 1987}年に引用古典に選ばれ、 JMムーアと共著で動的計画法 に関する影響力のある初期の論文も執筆した。^{[2] [11]ローラーは、}マトロイド交差が多項式時間で解けることを初めて観察した人物でもある。^{[1] [12]}

カープの21のNP完全問題のうちの2つの問題、有向ハミルトン閉路と3次元マッチングのNP完全性の証明は、カープによってローラーに帰された。^[1] 3次元マッチングのNP完全性は、ローラーのお気に入りの観察の1つである「2つの神秘的な力」の例である。^[1]整数でパラメータ化できる多くの組み合わせ最適化問題では、パラメータが2のときは多項式時間で問題を解くことができるが、パラメータが3のときはNP完全になる。3次元マッチングの場合、パラメータ2で解ける問題はグラフマッチングである。グラフの2色塗りと3色塗りの複雑さ、2つまたは3つのマトロイドの交差に対するマトロイド交差問題、および充足可能性問題に対する2-SATと3-SATで同じ現象が発生する。レンストラ^[1]は、「ジーン氏はいつも、これが二つの性別を持つ世界が考案された理由だとコメントしていた」と書いている。

1970年代、ローラーはジョブショップスケジューリングのアルゴリズムの体系化に大きな進歩を遂げました。^{[1] 1979年のこのテーマに関する調査では、}理論的なスケジューリング問題に3フィールド表記法を導入し、これは（以前の表記法が存在していたにもかかわらず）スケジューリングアルゴリズムの研究の標準となりました。 [ ^{13] [14]}後の別の調査も非常に引用されています（Google Scholarでそれぞれ1000件以上の引用）。^[15]

1980年代後半、ローラーは進化樹の再構築や配列アライメントに関するいくつかの研究を含む計算生物学の問題に研究の焦点を移しました。^[2]

1969年春、バークレーで休暇を取っていたローラーはベトナム戦争に反対する抗議活動に参加し、ローラーを含む483人の抗議者が逮捕された。^[3] リチャード・カープが彼を保釈した。^[6] カープはローラーを「コンピューターサイエンス部門の社会的良心であり、常に学生の福祉に気を配り、特に女性、少数民族、障害のある学生を気遣っていた」と回想している。^[6]

1998年には、雑誌『数理計画論』の特別号（第82巻第1号～第2号）がローラーを称えて刊行された。^[8]

ACMユージン・L・ローラー賞は、計算機科学と情報科学における人道的貢献に対して、計算機協会によって2年ごとに授与されます。 ^[16]

• 組み合わせ最適化: ネットワークとマトロイド(Holt、Rinehart、Winston 1976、^[17] ISBN  978-0-03-084866-7、2001年にDover Booksから再出版、ISBN 978-0-486-41453-9 )。LenstraとShmoysは、この本は古典であり、「新しい研究分野の形成に貢献した」と書いています。^[8] 
• 巡回セールスマン問題: 組み合わせ最適化のガイドツアー( JK Lenstra、AHG Rinnooy Kan、D. Shmoys との共著、Wiley、1985 年、ISBN 978-0-471-90413-7 )。 
• Eugene L. Lawler の厳選された出版物( K. Aardal、JK Lenstra、F. Maffioli、およびD. Shmoys編、CWI Tracts 126、Centrum Wiskunde & Informatica、1999、ISBN 978-90-6196-484-1 )。ローラーの研究論文 26 件の再版。 

• 1977年のローラー、オーバーヴォルフアッハ写真コレクションより