This project studies approximation algorithms for NP-Hard optimization problems. Many of these are important, real-world problems. Because for these problems there probably are no efficient, exact algorithms, the project studies approximation algorithms. These algorithms are guaranteed to be fast and to return a near-optimal answer. Either this near-optimal solution can be used directly, or it can be used as a starting point for a heuristic which attempts to improve the solution. Among the problems studied are MAX SAT, the problem of satisfying as many disjunctions as possible in a given set of disjunctions of Boolean literals, variants of MULTICUT, which involve finding, in a graph, a smallest set of edges whose removal disconnects given vertices; and STEINER TREE, the problem, given a graph, of finding a cheap subgraph which connects a given set of terminals.
