ON AN APPROXIMATION MEASURE FOUNDED ON THE LINKS BETWEEN OPTIMIZATIONAND POLYNOMIAL-APPROXIMATION THEORY

In order to define a polynomial approximation theory linked to combina torial optimization closer than the existing one, we first formally de fine the notion of a combinatorial optimization problem and then, base d upon this notion, we introduce a notion of equivalence among optimiz ation problems. This equivalence includes, for example, translation or affine transformation of the objective function or yet some aspects o f equivalencies between maximization and minimization problems (for ex ample, the equivalence between minimum vertex cover and maximum indepe ndent set). Next, we adress the question of the adoption of an approxi mation ratio respecting the defined equivalence. We prove that an appr oximation ratio defined as a two-variable function cannot respect this equivalence. We then adopt a three-variable function as a new approxi mation ratio (already used by a number of researchers), which is coher ent 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 pr oblems.