Reductions That Preserve Approximability

Authored by: Giorgio Ausiello , Vangelis Th. Paschos

Handbook of Approximation Algorithms and Metaheuristics, Second Edition

Print publication date:  May  2018
Online publication date:  May  2018

Print ISBN: 9781498770118
eBook ISBN: 9781351236423
Adobe ISBN:


 Download Chapter



The technique of transforming a problem into another in such a way that the solution of the latter entails, somehow, the solution of the former, is a classical mathematical technique that has found wide application in computer science since the seminal works of Cook [1] and Karp [2] who introduced particular kinds of transformations (called reductions) with the aim of studying the computational complexity of combinatorial decision problems. The interesting aspect of a reduction between two problems consists in its twofold application: on one side it allows to transfer positive results (resolution techniques) from one problem to the other and, on the other side, it may also be used for deriving negative (hardness) results. In fact, as a consequence of such seminal work, by making use of a specific kind of reduction, the polynomial-time Karp-reducibility, it has been possible to establish a complexity partial order among decision problems, which, for example, allows us to state that, modulo polynomial-time transformations, the stisfiability problem is as hard as thousands of other combinatorial decision problems, even though the precise complexity level of all these problems is still unknown.

Search for more...
Back to top

Use of cookies on this website

We are using cookies to provide statistics that help us give you the best experience of our site. You can find out more in our Privacy Policy. By continuing to use the site you are agreeing to our use of cookies.