近似アルゴリズムパート I

説明

近似アルゴリズム、パート I

物体を最小限の数の箱にどれだけ効率的に詰めることができるでしょうか? ノードをどの程度うまくクラスタリングして、ネットワークをいくつかの中心を中心とするコンポーネントに安価に分割できるでしょうか? これらは、NP 困難な組み合わせ最適化問題の例です。このような問題を効率的に解決することはおそらく不可能であるため、私たちの目的は、多項式時間で計算でき、同時に最適値と比較したコストについて証明可能な保証を持つ近似解を提供することです。

このコースは、標準的な学部のアルゴリズムコースの知識を前提としており、この分野で人気があり驚くほど成功している手法である線形計画法を使用して設計できるアルゴリズムに特に重点を置いています。このコースを受講すると、理論的なコンピューターサイエンスの基礎にあるさまざまな問題と、強力な設計および分析のテクニックに触れることができます。完了すると、新しい組み合わせ最適化問題に直面したときに、それが数少ない既知の基本問題の XNUMX つに近いかどうかを認識できるようになり、線形計画法緩和を設計し、ランダム化された丸めを使用して問題を解決できるようになります。自分自身の問題。コースの内容、特に宿題は理論的なものであり、プログラミングの課題はありません。

これは、近似アルゴリズムに関する XNUMX 部構成のコースの最初のコースです。