Improved approximation algorithms for optimization problems in graphs with superlogarithmic treewidth
In this paper we present two novel generic schemes for approximation algorithms for optimization NP-hard graph problems constrained to partial k-trees. Our first scheme yields deterministic polynomial-time algorithms achieving typically an approximation factor of k/log(1-is an element of)n, where k = polylog(n). The second scheme yields randomized polynomial-time algorithms achieving an approximat
