Show simple item record

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

dc.contributor.authorDemange, Marc
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2010-02-02T14:38:23Z
dc.date.available2010-02-02T14:38:23Z
dc.date.issued1996
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3219
dc.language.isoenen
dc.subjectoptimizationen
dc.subject.ddc003en
dc.titleOn an approximation measure founded on the links between optimization and polynomial approximation theoryen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenIn 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.en
dc.relation.isversionofjnlnameTheoretical Computer Science
dc.relation.isversionofjnlvol158en
dc.relation.isversionofjnlissue1-2en
dc.relation.isversionofjnldate1996-05
dc.relation.isversionofjnlpages117-141en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/0304-3975(95)00060-7en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record