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
TypeArticle accepté pour publication ou publié
Journal nameFoundations of Computing and Decision Sciences
Poznań University of Technology
MetadataShow full item record
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 / Keywordspolynomial time approximation; polynomial reduction; NP-complete problem
Showing items related by title and author.
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
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é
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é