Approximation Algorithms for NP-Problems

Algorithms are at the heart of problem solving in scientific computing and computer science. Unfortunately many of the combinatorial problems that arise in a computational context are NP-hard, so that optimal solutions are unlikely to be found in polynomial time. How can we cope with this intractability? One approach is to design algorithms that find approximate solutions guaranteed to be within some factor of the quality of the optimal solution. More recently, in large-scale scientific computing, even polynomial time algorithms that find exact solutions are deemed too expensive to be practical, and one needs faster (nearly linear time) approximation algorithms. We will consider the design of approximation algorithms for various graph-theoretical and combinatorial problems that commonly arise in scientific computing and computational biology. These include set covers (vertex covers in hypergraphs), matching, coloring, and multiple sequence alignments in computational biology.