On an approximation measure founded on the links between optimization and polynomial approximation theory

AbstractIn order to define a polynomial approximation theory linked to combinatorial optimization closer than the existing one, we first formally define the notion of a combinatorial optimization problem and then, based upon this notion, we introduce a notion of equivalence among optimization problems. This equivalence includes, for example, translation or affine transformation of the objective function or yet some aspects of equivalencies between maximization and minimization problems (for example, the equivalence between minimum vertex cover and maximum independent set). Next, we adress the question of the adoption of an approximation ratio respecting the defined equivalence. We prove that an approximation ratio defined as a two-variable function cannot respect this equivalence. We then adopt a three-variable function as a new approximation ratio (already used by a number of researchers), which is coherent to the equivalence and, under the choice of the variables, the new ratio is introduced by an axiomatic approach. Finally, using the new ratio, we prove approximation results for a number of combinatorial problems