May 25-30, 2014
University Residential Center
Bertinoro (Forlì-Cesena), Italy
Two well known paradigms for solving NP-hard proplems are exact computation and polynomial time approximation. While the former relaxes the requirement that the running time is polynomial in the input size, the latter relaxes the requirement that the algorithm produces an optimum solution, and our main goal is to design a polynomial-time algorithm. The parallel studies of these paradigms have reached hardness of approximation barriers and highly impractical running times of the best known exact algorithms for NP-hard problems. These hardness results cannot be overcome by applying classic complexity measures.A refined analysis of running time can be achieved through parameterization. Parameterized complexity is concerned with a multivariate analysis of computational complexity, where in addition to the overall instance size, one takes account of the influence on computational complexity of secondary measurements. Most of the earlier work in parameterized complexity has focused on obtaining a refined classification for the hardness of optimization problems (using the W-hardness hierarchy), and on designing exact algorithms for NP-hard problems which are fixed parameter tractable.