Show simple item record

dc.contributor.authorPaschos, Vangelis
dc.contributor.authorRenotte, Laure
dc.date.accessioned2010-07-06T14:40:17Z
dc.date.available2010-07-06T14:40:17Z
dc.date.issued1995
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/4561
dc.language.isoenen
dc.subjectpolynomial time approximationen
dc.subjectpolynomial reductionen
dc.subjectNP-complete problemen
dc.subject.ddc003en
dc.titleApproximability preserving reductions for NP-complete problemsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe conceive some approximability preserving (continuous) reductions among a number of combinatorial problems. The preservation of the approximation ratio along these reductions establishes a kind of continuity between the involved problems, continuity resulting to a possible transfer (up to multiplication by the so called expansion of the reduction) of positive, negative or conditional results along chains of such reductions. We are, more particularly interested in continuity of reductions in the interior of hierarchies of combinatorial problems as well as, given that approximability preserving reductions are composable and transitive, we explore the continuity of reductions between members of different hierarchies. For a combinatorial problem, a hierarchy is obtained when we impose additional restrictions on its instances. We construct first a hierarchy for set covering problem and we explore the completeness of its members under reductions that preserve their approximation ratio (continuous reductions). We construct also a hierarchy for hitting set and we give continuity results for it. Moreover, we relate another NP-complete database query optimization problem, the minimal join problem to set covering hierarchy by proposing a reduction and by proving its continuity. After, we establish hierarchies for the vertex covering by cliques problem as well as for the vertex covering problem. For the members of each hierarchy we investigate the continuity of reductions relating them. Also, we propose such reductions connecting problems from distinct hierarchies. So, subclasses of NP-complete problems related by approximability preserving reductions are systematically constructed.en
dc.relation.isversionofjnlnameFoundations of Computing and Decision Sciences
dc.relation.isversionofjnlvol20en
dc.relation.isversionofjnlissue1en
dc.relation.isversionofjnldate1995
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherPoznań University of Technologyen
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record