• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

Approximability preserving reductions for NP-complete problems

Paschos, Vangelis; Renotte, Laure (1995), Approximability preserving reductions for NP-complete problems, Foundations of Computing and Decision Sciences, 20, 1

View/Open
publi176.pdf (275.6Kb)
Type
Article accepté pour publication ou publié
Date
1995
Journal name
Foundations of Computing and Decision Sciences
Volume
20
Number
1
Publisher
Poznań University of Technology
Metadata
Show full item record
Author(s)
Paschos, Vangelis
Renotte, Laure
Abstract (EN)
We 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.
Subjects / Keywords
polynomial time approximation; polynomial reduction; NP-complete problem

Related items

Showing items related by title and author.

  • Thumbnail
    On the approximation of NP-complete problems by using Boltzmann machine method. The cases of some covering and packing problems 
    Zissimopoulos, Vassilis; Paschos, Vangelis; Pekergin, Ferhan (1991) Communication / Conférence
  • Thumbnail
    On the approximation of NP-complete problems by using Boltzmann machine method: the cases of some covering and packing problems 
    Zissimopoulos, Vassilis; Paschos, Vangelis; Pekergin, Ferhan (1991) Article accepté pour publication ou publié
  • Thumbnail
    Approximation preserving reductions for set covering, vertex covering and independent set hierarchies under differential approximation 
    Ekim, Tinaz; Paschos, Vangelis (2004) Article accepté pour publication ou publié
  • Thumbnail
    An Introduction to Exponential Time Exact Algorithms for Solving NP-hard Problems 
    Paschos, Vangelis; Escoffier, Bruno; Bourgeois, Nicolas (2011) Chapitre d'ouvrage
  • Thumbnail
    Worst-case complexity of exact algorithms for NP-hard problems 
    Della Croce, Federico; Escoffier, Bruno; Kaminski, Marcin; Paschos, Vangelis (2008) Chapitre d'ouvrage
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo