CS 6320 - Intractable Problems and Approximation Algorithms

The course covers the theory of NP-completeness and techniques that help to apply the theory to practical problems. The model of non-deterministic Turing machines is used to classify various problems as NP (Non-deterministic Polynomial), Polynomial, NP-Complete, NP-Hard, and Pseudo-Polynomial. Problems in various computer science areas, such as scheduling, routing, compiler optimization, chip packaging, graph embedding, are used to illustrate the concepts and techniques. Effective approximation algorithms are designed and analyzed to deal with various NP-complete problems.

Prerequisites/Corequisites: Prerequisite: (CS 4310 or CS 5310) and CS 5800, a grade or “B” of better is required to satisfy any course prerequisite.

Credits: 3 hours

Restrictions This course is restricted to the following: masters and doctorates in computer science, masters in electrical engineering, and doctorates in mathematics.
Notes: Open to graduate students only.