Approximation Algorithms Courses and Certifications

IIT Kharagpur;  NPTEL

Selected Topics in Algorithms

Advanced algorithm design techniques for efficient problem-solving in computer science. Covers network flows, randomization, approximation algorithms, and parameterized algorithms for various applications.

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

IEEE

On Light Spanners, Low-Treewidth Embeddings and Efficient Traversing in Minor-Free Graphs

Explore efficient graph traversal techniques using light spanners and low-treewidth embeddings, with applications to minor-free graphs and approximation algorithms.

• YouTube
• 24 minutes
• On-Demand
• Conference Talk

IEEE

Stochastic Weighted Matching - 1-Epsilon Approximation

Explore stochastic weighted matching algorithms, including Monte Carlo analysis, vertex-independent matching, and greedy approaches for efficient approximation solutions.

• YouTube
• 29 minutes
• On-Demand
• Conference Talk

IEEE

A Parameterized Approximation Scheme for Min k-Cut

Explore a parameterized approximation scheme for the Min k-Cut problem, covering algorithms, research directions, and proof ingredients like tree decomposition and polynomial time analysis.

• YouTube
• 21 minutes
• On-Demand
• Conference Talk

Association for Computing Machinery (ACM)

Asymmetric Traveling Salesman Problem: Advances and Challenges - Session 1A

Explore cutting-edge research on the Asymmetric Traveling Salesman Problem, including algorithms, lower bounds, and approximation results in this advanced theoretical computer science talk.

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

Association for Computing Machinery (ACM)

Constant Girth Approximation for Directed Graphs in Subquadratic Time

Explore subquadratic-time algorithms for approximating constant girth in directed graphs, covering ball growing techniques, random sampling, and combined approaches for efficient graph analysis.

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

IEEE

Cut-Equivalent Trees are Optimal for Min-Cut Queries

Explore cut-equivalent trees and their optimality for min-cut queries, covering algorithms, data structures, and approximation techniques in graph theory.

• YouTube
• 24 minutes
• On-Demand
• Conference Talk

IEEE

Towards Better Approximation of Graph Crossing Number

Explores advanced techniques for approximating graph crossing numbers, focusing on new frameworks and theorems for both general and bounded-degree graphs.

• YouTube
• 26 minutes
• On-Demand
• Conference Talk

IEEE

Optimal Streaming Approximations for All Boolean Max 2-CSPs and Max k-SAT

Explore streaming approximations for Boolean Max 2-CSPs and Max k-SAT, covering algorithms, lower bounds, and communication complexity in constraint satisfaction problems.

• YouTube
• 25 minutes
• On-Demand
• Conference Talk

IEEE

Inapproximability of Clustering in Lp Metrics

Explores computational complexity of clustering in Lp metrics, discussing approximation algorithms, hardness of approximation, and key concepts like Johnson Coverage Hypothesis.

• YouTube
• 21 minutes
• On-Demand
• Conference Talk

Simons Institute

A Slightly Improved Approximation Algorithm for Metric TSP

Explore an improved approximation algorithm for the Metric Traveling Salesman Problem, focusing on 2-uniform spanning trees and probabilistic techniques in algorithm design.

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

Simons Institute

Crash Course on Probabilistically Checkable Proofs - Introduction

Explore probabilistically checkable proofs, including recoloring, constraint satisfaction, and the PCP theorem. Learn about verifier parameters and hardness of approximation in this comprehensive introduction.

• YouTube
• 1 hour 1 minute
• On-Demand
• Free Video

Simons Institute

A Brief Introduction to Algorithms, Game Theory and Risk-Averse Decision Making

Explore algorithms, game theory, and risk-averse decision making, covering shortest paths, NP-Complete problems, equilibria, and various risk frameworks for real-world applications.

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

Hausdorff Center for Mathematics

Recent Hardness of Approximation Results in Parameterized Complexity

Survey of recent hardness of approximation results in parameterized complexity, focusing on k-clique problem inapproximability, with technical insights and open problems discussion.

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

Hausdorff Center for Mathematics

LP-Norm Multiway Cut

Explores graph partitioning with lp-norm multiway cut, unifying min-sum and min-max variants. Discusses hardness, integrality gap, and approximation algorithm for this generalized problem.

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