Approximation algorithms on clusters: high-performance computing on cheap workstations

Many practical and important optimization problems turned out to be NP-complete. This implies that – unless P is not NP-- these problems are computationally intractable for problem instances of any significant size. In such cases one can sacrifice optimality and starts looking for approximate solutions that are computable in polynomial time (with respect to the problem size). However, an approximation algorithm, though polynomial with respect to the problem size, may exhibit superpolinomial (e.g. exponential) time complexity with respect to the required accuracy of the approximate solutions. Informally, this means that improving the accuracy of the solution quickly becomes a very costly task in terms of computational time. Thus, accuracy improvement for such problems is practically infeasible and can be carried further on (up to a certain point) only by means of a high-performance computing system. Alternatively, a more cost effective solution is to use a cluster, that is, a set of relatively cheap interconnected workstations. In our project, we will form a cluster and then determine the extent to which approximation algorithms for some practical problems (e.g. partitioning problems) are capable of exploiting cluster computing.