COM SCI 280AP

Main Course

Algorithms: Approximation Algorithms

Description

Lecture, four hours; outside study, eight hours. Requisite: course 180. Background in discrete mathematics helpful. Theoretically sound techniques for dealing with NP-Hard problems. Inability to solve these problems efficiently means algorithmic techniques are based on approximation-finding solution that is near to best possible in efficient running time. Coverage of approximation techniques for number of different problems, with algorithm design techniques that include primal-dual method, linear program rounding, greedy algorithms, and local search. Letter grading.

Prerequisites

• Required: COM SCI 180

  Plan

  Taken?