デビッド・シュモイズ

デビッド・シュモイズ
デビッド・シュモイズ
生まれる	1959年（64～65歳）
母校	プリンストン、 カリフォルニア大学バークレー校
受賞歴	フレデリック・W・ランチェスター賞 （2013年） ダニエル・H・ワグナー賞（2018年） カチヤン賞（2022年）
科学者としてのキャリア
フィールド	コンピュータサイエンス、計算複雑性理論
機関	コーネル
論文	シーケンス、スケジューリング、通信ネットワーク設計の問題に対する近似アルゴリズム (1984)
博士課程の指導教員	ユージン・ローラー
博士課程の学生	クリフォード・スタイン
Webサイト	people.orie.cornell.edu/shmoys/

デビッド・バーナード・シュモイズ（1959年生まれ）は、コーネル大学のオペレーションズリサーチおよび情報工学学部とコンピュータサイエンス学部の教授です。1984年にカリフォルニア大学バークレー校で博士号を取得しました。主な研究分野は、離散最適化問題の アルゴリズムの設計と分析です。

特に、彼の研究は、NP困難な問題に対する近似アルゴリズムの設計における線形計画法の役割を強調しています。彼は、k中心問題とk中央値問題、一般化割り当て問題など、いくつかのスケジューリング問題とクラスタリング問題に対する最初の定数因子パフォーマンス保証を提供する先駆的な研究で知られています。彼がスケジューリング問題のために開発した多項式時間近似スキームは、その後の多くの研究に応用されています。彼の現在の研究には、COVID疫学的モデリング、議会の選挙区割り、輸送、IoTネットワーク設計など、幅広い分野におけるデータ駆動型モデルの確率的最適化が含まれます。シュモイズは、コーネル大学のジェイコブ・グールド・シュルマンコンピューターサイエンス教授である エヴァ・タルドスと結婚しています。

彼の重要な貢献の2つは

1. 一般化割り当て問題と無関係な並列マシン スケジューリングのための定数係数近似アルゴリズム。
2. k-中央値と施設配置問題のための定数係数近似アルゴリズム。

これらの貢献について以下に簡単に説明します。

論文^[1]はDavid ShmoysとEva Tardosの共同研究です。

一般化された割り当て問題は、無関係な並列マシンをコストとともにスケジュールする次の問題として考えることができます。 独立したジョブ ( と表記) のそれぞれは、無関係な並列マシン ( と表記)の 1 つで処理される必要があります。無関係とは、同じジョブが異なるマシンでは異なる処理時間を要する可能性があることを意味します。ジョブは、マシンで処理されるときに時間単位を要し、コスト が発生します。および が与えられた場合 、各マシンの負荷に対して、割り当てられたジョブに必要な合計処理時間が最大で となるような、合計コストが最大で のスケジュールが存在するかどうかを判断します。処理時間をスケーリングすることにより、一般性を失うことなく、マシン負荷の境界が を満たすと想定できます。「言い換えると、一般化された割り当て問題は、メイクスパン、最大マシン負荷が最大であるという制約の下で、コストが最小のスケジュールを見つけることです」。 ${\displaystyle n}$${\displaystyle J}$${\displaystyle m}$${\displaystyle M}$${\displaystyle j}$${\displaystyle p_{i,j}}$${\displaystyle i}$${\displaystyle c_{i,j},i=1,2,..,m;j=1,2,..,n;n\geq m}$${\displaystyle C}$${\displaystyle T_{i},i=1,2,..,m}$${\displaystyle C}$${\displaystyle i}$${\displaystyle T_{i},i=1,2,..,m}$${\displaystyle T_{1}=T_{2}=..=T_{m}=T}$${\displaystyle T}$

ここで引用した Shmoys とLenstra、Tardosの研究^[2] では、単位コストの場合の 2 近似アルゴリズムが示されています。このアルゴリズムは、パラメトリック プルーニングを使用した線形計画の巧妙な設計と、線形計画の極値点の解を決定論的に丸めるという手法に基づいています。一般化割り当て問題のアルゴリズムは、同様の LP をパラメトリック プルーニングで実行し、慎重に設計された二部グラフで新しい丸め手法を使用することに基づいています。ここでは、LP の定式化を述べ、丸め手法について簡単に説明します。

メイクスパンの最適値を推測し、次の LP を記述します。この手法はパラメトリック プルーニングとして知られています。 ${\displaystyle T}$

${\displaystyle LP(T)::\sum _{i=1}^{m}\sum _{j=1}^{n}c_{ij}x_{ij}\leq C}$;

${\displaystyle \sum _{i=1}^{m}x_{ij}=1\qquad j=1,\ldots ,n}$;

${\displaystyle \sum _{i=1}^{m}p_{ij}x_{ij}\leq T\qquad i=1,\ldots ,m}$;

${\displaystyle x_{ij}\geq 0\qquad i=1,\ldots ,m,\quad j=1,\ldots ,n}$;

${\displaystyle x_{ij}=0\qquad {\text{if}}\qquad p_{ij}\geq T,\qquad i=1,\ldots ,m,\quad j=1,\ldots ,n}$;

得られた LP 解は、次のように整数解に丸められます。重み付き二部グラフ が構築されます。二部グラフの片側にはジョブ ノード が含まれ、もう一方の側には各マシン ノード のいくつかのコピー が含まれます 。ここで、です。たとえばマシン に対応するマシン ノードへのエッジを構築するには、まずジョブを処理時間の降順で並べます。簡単にするために、 と仮定します。次に、となる 最小のインデックス を見つけます。 を以外のすべてのエッジに含め、それらの重みを に設定します。エッジ を作成し 、その重みを に設定します。これにより、頂点に接するエッジの合計重みが最大で 1 になることが保証されます。 の場合、重み のエッジを作成します。同様の方法で、 へのエッジの割り当てを続けます。${\displaystyle G=(W\cup V,E)}$${\displaystyle W=\{w_{j}|j\in J\}}$${\displaystyle V=\{v_{i,s}|i=1,2,..,m;s=1,2,..,k_{i}\}}$${\displaystyle k_{i}=\lceil \sum _{j}x_{ij}\rceil }$${\displaystyle i}$${\displaystyle p_{ij}}$${\displaystyle p_{i1}\geq p_{i2}\geq \ldots \geq p_{in}}$${\displaystyle j_{1}}$${\displaystyle \sum _{j=1}^{j_{1}}x_{ij}\geq 1}$${\displaystyle E}$${\displaystyle (w_{j},v_{i1},j=1,2,..,j_{1}-1)}$${\displaystyle x_{ij}}$${\displaystyle x'_{v_{i1}j}=x_{ij}}$${\displaystyle (w_{j_{1}},v_{i1})}$${\displaystyle x'_{v_{i1}j_{1}}=1-\sum _{i=1}^{j_{1}-1}x'_{v_{i1}j}}$${\displaystyle v_{i1}}$${\displaystyle x'_{v_{i1}j_{1}}<x_{ij_{1}}}$${\displaystyle (w_{j_{1}},v_{i2})}$${\displaystyle x'_{v_{i2}j_{1}}=x_{ij}-x'_{v_{i1}j_{1}}}$${\displaystyle v_{i2}}$

このようにして作成された二部グラフでは、 の各ジョブ ノードには合計エッジ ウェイトが 1 インシデントあり、 の各マシン ノードには合計ウェイトが最大で 1 インシデントのエッジがあります。したがって、ベクトルは の分数マッチングのインスタンスであり、丸めて同じコストの整数マッチングを取得できます。 ${\displaystyle W}$${\displaystyle V}$${\displaystyle x'}$${\displaystyle G}$

ここで、構築中のマシン ノード上のジョブの処理時間の順序を考慮し、簡単な課金引数を使用すると、次の定理が証明されます。 ${\displaystyle G}$

定理:に実行可能な解がある場合、メイクスパンとコストを使用してスケジュールを作成できます 。 ${\displaystyle LP(T)}$${\displaystyle T+max_{i,j}p_{i,j}}$${\displaystyle C}$

なので、2の近似値が得られます。 ${\displaystyle max_{i,j}p_{i,j}\leq T}$

論文^[3]は、 Moses Charikar、Sudipto Guha、Éva Tardos、David Shmoysによる共同研究です。彼らは、メトリックk中央値問題の近似値を得ました。これは、それまで最もよく知られていた近似値を破った最初の論文でした。 ${\displaystyle 6{\frac {2}{3}}}$${\displaystyle O(\log {k}\ \log {\log {k}})}$

Shmoys は、施設配置問題にも幅広く取り組んできました 。彼の最近の成果には、容量制限のある施設配置問題の近似アルゴリズムの取得が含まれています。Fabian Chudak との共同研究^[4]により、同じ問題に対する従来の既知の近似が改善されました。彼らのアルゴリズムは、バックアップ付きランダム化丸めと呼ばれるランダム化丸めのバリエーションに基づいています。これは、通常のランダム化丸めでは、関連する集合被覆問題に対して実行可能なソリューションがほとんど生成されないという事実を修正するためにバックアップ ソリューションが組み込まれているためです。 ${\displaystyle 3}$${\displaystyle 5.69}$

施設配置問題の無能力バージョンについては、再びChudakとの共同研究^[5]で、彼は、従来の近似保証を大幅に改善した近似アルゴリズムを得ました。改善されたアルゴリズムは、線形計画緩和の最適分数解を丸め、線形計画の最適解の特性と分解手法の一般化を使用することで機能します。 ${\displaystyle (1+2/e)\approx 1.736}$

David Shmoys は、ACM フェロー、SIAM フェロー、およびオペレーションズ リサーチおよび経営科学研究所(INFORMS)フェロー(2013 年) です。コーネル大学工学部から Sonny Yau Excellence in Teaching Award を 3 回受賞したほか、NSF Presidential Young Investigator Award、Frederick W. Lanchester Prize (2013 年)、Daniel H. Wagner Prize in Excellence in the Practice of Advanced Analytics and Operations Research (2018 年)、および最適化分野での生涯にわたる功績に対して毎年授与される INFORMS Optimization Society の Khachiyan Prize (2022 年) を受賞しています。

• David Shmoys のホームページ
• エヴァ・タルドスのホームページ