Approximation Algorithms Courses and Certifications

PapersWeLove

Bin Packing Can Be Solved Within 1 + ε in Linear Time - Lecture

Explore bin packing optimization with Yiduo Ke, delving into a linear-time solution within 1 + ε. Gain insights into this fundamental problem's applications and theoretical advancements.

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

Google TechTalks

A Constant Factor Prophet Inequality for Online Combinatorial Auctions

Explore constant factor prophet inequalities for online combinatorial auctions with subadditive valuations. Learn about the Mirror Lemma and Kakutani's fixed point theorem application.

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

Institut des Hautes Etudes Scientifiques (IHES)

Euclidean Capacitated Vehicle Routing in Random Setting - A 1.55-Approximation Algorithm

Explore a 1.55-approximation algorithm for Euclidean capacitated vehicle routing in random settings, presented by Zipei Nie.

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

BIMSA

Classic Problems with Modern Techniques - Prize-collecting Framework

Explore state-of-the-art approximation algorithms for classic network design problems using modern techniques, from clustering to recursive methodologies.

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

Shortest Paths Revisited, NP-Complete Problems and What To Do About Them

815 ratings at Coursera

Explore advanced graph algorithms, NP-completeness, and strategies for tackling computationally intractable problems. Learn Bellman-Ford, Floyd-Warshall, and heuristic approaches for complex algorithmic challenges.

• Coursera
• 13 hours 27 minutes
• On-Demand
• Free Online Course (Audit)

Design and Analysis of Algorithms

1 review

Comprehensive exploration of advanced algorithm design and analysis, covering diverse topics from interval scheduling to cryptography and distributed systems.

• MIT OpenCourseWare
• 39 hours
• On-Demand
• Free Video

Delivery Problem

372 ratings at Coursera

Implement efficient Python programs for the traveling salesman problem, exploring exact and approximation algorithms while applying discrete mathematics concepts.

• Coursera
• 13 hours 23 minutes
• On-Demand
• Free Online Course (Audit)

Approximation Algorithms and Linear Programming

38 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)

Approximation Algorithms Part I

553 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 9 hours 54 minutes
• On-Demand
• Free Online Course (Audit)

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 8 hours 30 minutes
• On-Demand
• Free Online Course (Audit)

Approximation Algorithms

32 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)

NPTEL;  IIT Bombay

Design & Analysis of Algorithms

2 reviews

Comprehensive exploration of algorithm design techniques, analysis frameworks, and problem-solving strategies, covering divide-and-conquer, greedy algorithms, dynamic programming, and NP-completeness.

• YouTube
• 1 day 6 hours
• On-Demand
• Free Video

NPTEL;  IIT Bombay

Design and Analysis of Algorithms

Comprehensive exploration of algorithm design techniques, analysis frameworks, and problem-solving strategies, covering divide-and-conquer, greedy algorithms, dynamic programming, and NP-completeness.

• YouTube
• 1 day 6 hours
• On-Demand
• Free Video

NPTEL;  IIT Kanpur

Computer Algorithms - 2

The course discusses efficient algorithms from a large number of domains. This course assumes the knowledge of data structures, the knowledge big-O notation and the concept of time and space complexity of an algorithm.

• YouTube
• 1 day 6 hours
• On-Demand
• Free Video

IIT Kharagpur;  NPTEL

Approximation Algorithm

Explore efficient algorithms for NP-complete problems, covering vertex cover, set cover, knapsack, linear programming, rounding techniques, primal-dual method, and semidefinite programming.

• Swayam
• 12 weeks
• On-Demand
• Free Online Course