On an approximation measure founded on the links between optimization and polynomial approximation theory
Demange, Marc; Paschos, Vangelis (1996), On an approximation measure founded on the links between optimization and polynomial approximation theory, Theoretical Computer Science, 158, 1-2, p. 117-141. http://dx.doi.org/10.1016/0304-3975(95)00060-7
TypeArticle accepté pour publication ou publié
Journal nameTheoretical Computer Science
MetadataShow full item record
Abstract (EN)In 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.
Subjects / Keywordsoptimization
Showing items related by title and author.
Quelques étapes vers la conciliation de la théorie d'approximation et celle d'optimisation : une nouvelle théorie d'approximation polynomiale et résultats préliminaires Demange, Marc; Paschos, Vangelis (1993) Article accepté pour publication ou publié