Mihalis Yannakakis

ジェフリー・ウルマン 2002年 - クリストス・パパディミトリウ 2003年 - アイタイ・ミクローシュ（英語版） 2005年 - Mihalis Yannakakis 2007年 - ナンシー・リンチ 2008年 - フォルカー・シュトラッセン 2010年 - デイヴィッド・S・ジョンソン（英語版）

000ドル、メダルおよび賞状が与えられている。 2024年 Jim Dai 2023年 クリストス・パパディミトリウ、Mihalis Yannakakis 2022年 Vijay Vazirani 2021年 Alexander Shapiro 2020年 en:Adrian Lewis

の各辺の両端の少なくとも一方を含む。まとめると、集合 C は最小頂点被覆に対して高々2倍の大きさに収まる。 この単純なアルゴリズムは、Fanica Gavril と Mihalis Yannakakis が発見した。 より複雑な技法を使うと、近似係数が若干よい近似アルゴリズムがあることが示される。例えば、近似係数 2 − Θ ( 1

グラフGとパラメタkが与えられたとき， Gが少なくとも長さkの誘導パスが存在するかを決定する問題は，NP完全である． この結果は，Mihalis Yannakakisの未発表の結果としてGarey & Johnson (1979)が紹介している． しかし，この問題はGが特定のグラフクラスであるときに，