آموزش الگوریتم‌های تقریبی - آخرین آپدیت

مقدمه‌ای بر الگوریتم‌های تقریبی Introduction to Approximation algorithms

• مقدمه‌ای بر الگوریتم‌های تقریبی Introduction to Approximation Algorithms

مسئله تعادل بار (Load Balancing) The Load Balancing problem

• یک الگوریتم حریصانه برای تعادل بار A greedy algorithm for load balancing

• تحلیل الگوریتم حریصانه Analysis of the greedy-algorithm

• الگوریتم زمان‌بندی مرتب‌شده The ordered scheduling algorithm

آرام‌سازی برنامه‌ریزی خطی (LP Relaxation) LP Relaxation

• مسئله پوشش رأس (Vertex Cover) The vertex-cover problem

• یک الگوریتم تقریبی برای پوشش رأس An approximation algorithm for vertex-cover

• مقدمه‌ای کوتاه بر برنامه‌ریزی خطی A brief introduction to linear programming

• پوشش رأس وزن‌دار Weighted vertex-cover

• آرام‌سازی LP برای پوشش رأس وزن‌دار LP relaxation for weighted vertex-cover

• آرام‌سازی LP: تحلیل نسبت تقریب LP relaxation: Analyzing approximation ratio

طرح‌های تقریبی زمان چندجمله‌ای (PTAS) Polynomial-time approximation schemes

• طرح‌های تقریبی زمان چندجمله‌ای Polynomial-time approximation schemes

• مسئله کوله‌پشتی (Knapsack) Knapsack Problem

• یک الگوریتم برنامه‌نویسی پویا برای کوله‌پشتی A dynamic-programming algorithm for knapsack

• یک طرح PTAS برای کوله‌پشتی A PTAS for knapsack

• تحلیل PTAS برای کوله‌پشتی: نسبت تقریب Analysis of the PTAS for knapsack: approximation ratio

• تحلیل PTAS برای کوله‌پشتی: زمان اجرا Analysis of the PTAS for knapsack: running time