BloomTech’s Downfall: A Long Time Coming

Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

Indian Institute of Technology, Kharagpur

Approximation Algorithm

Indian Institute of Technology, Kharagpur and NPTEL via Swayam

Go to class Write review

Overview

Limited-Time Offer: Up to 75% Off Coursera Plus!
7000+ certificate courses from Google, Microsoft, IBM, and many more.
India: 75% Off World: 40% Off
ABOUT THE COURSE: Many real-world problems are NP-complete. Hence, they are unlikely to admit a polynomial-time algorithm. In this course, we will study various techniques to design efficient algorithms to compute an approximately optimal solutions.INTENDED AUDIENCE: Under-graduate and post-graduate students and faculty members.PREREQUISITES: Knowledge of algorithm design principles.INDUSTRY SUPPORT: All software companies especially Google, Microsoft, etc.

Syllabus

Week 1: Review of NP-CompletenessWeek 2:Approximation algorithm for the vertex cover, set cover, and traveling salesman problemWeek 3:Approximation algorithm for the Knapsack problem and the job scheduling problemsWeek 4:Basics of linear programmingWeek 5:Deterministic rounding: set cover, vertex cover problemsWeek 6:Deterministic rounding: steiner tree, facility location problemsWeek 7:Randomized rounding: max-SAT problemWeek 8:Randomized rounding: steiner tree, facility location problemsWeek 9:Primal-dual method: set coverWeek 10:Primal-dual method: steiner treeWeek 11:Semidefinite programming: max cutWeek 12:Hardness of approximation: travelling salesman problem, job scheduling

Taught by

Prof. Palash Dey

Tags

Reviews

Start your review of Approximation Algorithm

Go to class

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Sign up for free
Someone learning on their laptop while sitting on the floor.