Approximation Algorithms Courses and Certifications

Association for Computing Machinery (ACM)

Approximation Algorithms

Explore approximation algorithms for network design, including connectivity augmentation, Steiner trees, and spectral rounding techniques. Learn about linear programming and future research directions.

• YouTube
• 41 minutes
• On-Demand
• Free Video

Ryan O'Donnell

Approximation Algorithms

Explore approximation algorithms for NP-hard problems, focusing on vertex cover, k-coverage, and traveling salesperson. Learn greedy approaches and their limitations, as well as more advanced techniques.

• YouTube
• 1 hour 14 minutes
• On-Demand
• Free Video

Ryan O'Donnell

Great Ideas in Theoretical Computer Science - Approximation Algorithms

Explore approximation algorithms for NP-hard problems, focusing on Vertex Cover, k-Coverage, and Traveling Salesperson. Learn techniques to find near-optimal solutions efficiently.

• YouTube
• 1 hour 20 minutes
• On-Demand
• Free Video

Fields Institute

Approximation Algorithms for Hitting Subgraphs

Explore approximation algorithms for hitting subgraphs, covering inapproximability, NP-hardness, and semi-symmetric cut vertices in this advanced combinatorial algorithms lecture.

• YouTube
• 29 minutes
• On-Demand
• Free Video

Hausdorff Center for Mathematics

Approximation Algorithms for Hard Augmentation Problems - Lecture III

Explore advanced network design techniques for increasing graph connectivity, focusing on recent approaches and advances in augmentation problems like Tree Augmentation and Connectivity Augmentation.

• YouTube
• 1 hour 18 minutes
• On-Demand
• Free Video

Hausdorff Center for Mathematics

Approximation Algorithms for Hard Augmentation Problems

Explore advanced network design techniques for increasing graph connectivity, focusing on augmentation problems and recent developments in combinatorial optimization.

• YouTube
• 1 hour 12 minutes
• On-Demand
• Free Video

IEEE

Approximation Algorithms for Stochastic Minimum Norm Combinatorial Optimization

Explore advanced techniques for solving stochastic minimum norm combinatorial optimization problems, focusing on approximation algorithms and their applications in complex decision-making scenarios.

• YouTube
• 22 minutes
• On-Demand
• Free Video

IEEE

Approximation Algorithms for LCS and LIS with Truly Improved Running Times

Explore advanced approximation algorithms for LCS and LIS, offering improved running times and enhanced computational efficiency in sequence analysis.

• YouTube
• 18 minutes
• On-Demand
• Free Video

École normale supérieure

Approximation Algorithms Part I

554 ratings at Coursera

Explore approximation algorithms for NP-hard problems using linear programming and randomized rounding techniques. Learn to design efficient solutions with provable guarantees for combinatorial optimization challenges.

• Coursera
• 1 day 12 hours 54 minutes
• On-Demand
• Free Online Course (Audit)

Approximation Algorithms and Linear Programming

44 ratings at Coursera

Explore linear and integer programming for optimal solutions in resource allocation, scheduling, and task assignment. Learn approximation algorithms for NP-hard problems with guaranteed performance bounds.

• Coursera
• 2 days 27 minutes
• On-Demand
• Free Online Course (Audit)

École normale supérieure

Approximation Algorithms Part II

44 ratings at Coursera

Explore advanced approximation algorithms using linear programming duality and semidefinite programming for combinatorial optimization problems like Steiner forest, facility location, and maximum cut.

• Coursera
• 1 day 11 hours 30 minutes
• On-Demand
• Free Online Course (Audit)

Approximation Algorithms

33 ratings at Coursera

Explore efficient approximation techniques for NP-hard problems, learning to design and analyze algorithms that find near-optimal solutions with provable performance guarantees.

• Coursera
• 14 hours 59 minutes
• On-Demand
• Free Online Course (Audit)

Association for Computing Machinery (ACM)

An Improved Approximation Algorithm for ATSP

Explore an advanced approximation algorithm for the Asymmetric Traveling Salesman Problem, covering linear programming relaxation, reductions, and recursive techniques to improve solution quality.

• YouTube
• 24 minutes
• On-Demand
• Free Video

Association for Computing Machinery (ACM)

Breaching the 2-Approximation Barrier for Connectivity Augmentation

Explore advanced techniques in network design, focusing on connectivity augmentation and its reduction to the Steiner Tree problem. Learn about novel approximation algorithms and open challenges in the field.

• YouTube
• 20 minutes
• On-Demand
• Free Video

Ryan O'Donnell

Hardness of Approximation - Part 1

Explore hardness of approximation in computational complexity, covering Max Cut, Independent Set, and K-Cover problems. Learn key definitions, algorithms, and current research state.

• YouTube
• 59 minutes
• On-Demand
• Free Video