COL754: Difference between revisions
| [checked revision] | [checked revision] |
Prashantt492 (talk | contribs) Creating course page via bot |
Bot: wrap bare course codes in wikilinks |
||
| Line 4: | Line 4: | ||
| credits = 3 | | credits = 3 | ||
| credit_structure = 3-0-0 | | credit_structure = 3-0-0 | ||
| pre_requisites = COL351 OR Equivalent | | pre_requisites = [[COL351]] OR Equivalent | ||
| overlaps = | | overlaps = | ||
}} | }} | ||
Latest revision as of 16:26, 14 April 2026
| COL754 | |
|---|---|
| Approximation Algorithms | |
| Credits | 3 |
| Structure | 3-0-0 |
| Pre-requisites | COL351 OR Equivalent |
| Overlaps | |
COL754 : Approximation Algorithms
NP-hardness and approximation algorithms. Different kinds of approximability. Greedy algorithm and local search with applications in facility location, TSP and scheduling. Dynamic programming with applications in knapsack, Euclidean TSP, bin packing. Linear programming, duality and rounding. Applications in facility location, Steiner tree and bin packing. Randomized rounding with applications. Primal-dual algorithms and applications in facility location and network design. Cuts and metrics with applications to multi-commodity flow. Semi-definite programming and applications: max-cut, graph coloring. Hardness of approximation.