We present two new combinatorial approximation frameworks that are not based on LP-duality, or even on linear programming. Instead, they are based on weight manipulation in the spirit of the local ratio technique. We show that the first framework is equivalent to the LP based method of dual fitting and that the second framework is equivalent an LP-based method which we define and call primal fitting.
Our equivalence results are not unlike the recently proven equivalence between the (combinatorial) local ratio technique and the (LP based) primal-dual schema. Although equivalent, the local ratio approach is more intuitive, and indeed, several breakthrough results were first obtained within the local ratio framework and only later translated into primal-dual algorithms. We believe that our frameworks may have a similar role with respect to their LP-based counterparts (dual fitting and primal fitting). Also, we think that the notion of primal fitting is of independent interest.
We demonstrate the frameworks by presenting alternative analyses to the greedy algorithm for the set cover problem, and to known algorithms for the metric uncapacitated facility location problem. Also, we analyze a 9-approximation algorithm for a disk cover problem that arises in the design phase of cellular telephone networks.