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

برنامه‌ریزی خطی Linear Programming

• مقدمه‌ای بر برنامه‌ریزی خطی Introduction to Linear Programming

• برنامه‌ریزی خطی چیست؟ What is a Linear Program?

• مثال: مسئله تقسیم کیک Example: Cake-Sharing Problem

• حل برنامه‌های خطی Solving Linear Programs

• مسائل جریان شبکه و برنامه‌ریزی خطی Network Flow Problems and Linear Programs

• هندسه برنامه‌های خطی Geometry of Linear Programs

• الگوریتم‌های حل برنامه‌های خطی Algorithms for Solving Linear Programs

برنامه‌ریزی خطی صحیح Integer Linear Programming

• برنامه‌ریزی خطی صحیح چیست؟ What is an Integer Linear Program?

• مقدمه رسمی برنامه‌ریزی خطی صحیح Formal Introduction to Integer Linear Programs

• سختی NP در برنامه‌ریزی خطی صحیح NP Hardness of Integer Linear Programming

• پوشش رأس به عنوان یک برنامه خطی صحیح Vertex Cover as an Integer Linear Program

• تقریب‌های برنامه‌ریزی خطی برای پوشش رأس Linear Programming Approximations to Vertex Cover

• الگوریتم شاخه و کران برای حل برنامه‌های خطی صحیح Branch and Bound Algorithm for Solving Integer Linear Programs

الگوریتم‌های تقریب: زمان‌بندی، پوشش رأس و MAX SAT Approximation Algorithms : Scheduling, Vertex Cover and MAX-SAT

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

• مقدمه‌ای بر زمان‌بندی کارگاهی و طراحی الگوریتم Introduction to Jobshop Scheduling and Algorithm Design

• تحلیل زمان‌بندی کارگاهی Analysis of Jobshop Scheduling

• الگوریتم‌های تقریب برای پوشش رأس و تحلیل آن‌ها Approximation Algorithms for Vertex Cover and their Analysis

• الگوریتم‌های تقریب برای مسئله بیشینه ارضای شرط (MAX SAT) Approximation Algorithms for the Maximum Satisfiability Problem

مسئله فروشنده دوره‌گرد (TSP) و طرح‌های تقریب Travelling Salesperson Problem (TSP) and Approximation Schemes

• مقدمه‌ای بر TSP و کاربردهای آن Introduction to TSP and its applications

• سختی NP در مسائل TSP NP-Hardness of TSPs

• سختی تقریب در مسائل TSP عمومی Hardness of Approximating General TSPs

• الگوریتم برنامه‌ریزی پویا هلد و کارپ Held and Karp's Dynamic Programming Algorithm

• فرمول‌بندی برنامه‌ریزی خطی صحیح Integer Linear Programming Formulation

• فرمول‌بندی زیرتورها و حذف زیرتور Subtours and Subtour Elimination Formulation

• TSP متریک و میان‌بر زدن Metric TSP and Shortcutting

• گشت‌های اویلری برای تقریب TSP Eulerian Walks for approximating TSPs

• الگوریتم کریستوفیدس و تحلیل آن Christofides Algorithm and its Analysis

• روش‌های هیوریستیک برای TSP Heuristics for TSPs

• طرح تقریب با زمان چندجمله‌ای کامل و کوله‌پشتی Full Polynomial Time Approximation Scheme and Knapsack