Research in these areas typically involves one or more of the following steps:

(i) identification of an interesting problem,
(ii) categorization of the problem according to its complexity status, and
(iii) searching for an efficient algorithm for handling the problem.

The goal is to devise algorithms having prescribed levels of efficiency. This includes polynomial time exact algorithms, improved exponential algorithms, approximation schemes and algorithms with probabilistic performance guarantees. Often, a theoretical understanding of a problem's structure plays an important role in the design of such algorithms. When the original problem is probably hard, a goal is to zero in on the boundary between the efficiently solvable special cases and the hard general case.


Loading ...