Divide-and-conquer approximation algorithms via spreading metrics

A novel divide-and-conquer paradigm for approximating NP-hard graph optimization problems is presented. The paradigm models graph optimization problems that satisfy two properties. First, a divide-and-conquer approach is applicable. Second, a fractional spreading metric is computable in polynomial time. The spreading metric assigns fractional lengths to either edges or vertices of the input graph, such that all subgraphs on which the optimization problem is non-trivial have large diameters. In addition, the spreading metric provides a lower bound on the cost of solving the optimization problem.