SOME STEPS TOWARDS THE CONCILIATION OF AP PROXIMATION AND OPTIMIZATION THEORY - A NEW SUGGESTED APPROXIMATION MEASURE AND PRELIMINARY-RESULTS

It is commonly known that a convenient way to express combinatorial pr oblems is to write them down as integer linear programs. In this conte xt, the theory of the polynomial approximation of NP-complete problems seems to be inadequate to capture the nature of the treated problems, as it is not able to capture in a global manner the equivalence, with respect to their approximation, of all the ways of expressing a given problem in terms of an integer program. This is our main motivation f or proposing a novel definition of the approximation measure. This pro cess includes a new formalism for the approximation theory as well as some results concerning this new measure.