Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Safe Approximation and Its Relation to Kernelization
verfasst von : Jiong Guo, Iyad Kanj, Stefan Kratsch
Erschienen in: Parameterized and Exact Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We introduce a notion of approximation, called
safe approximation
, for minimization problems that are subset problems. We first study the relation between the standard notion of approximation and safe approximation, and show that the two notions are different unless some unlikely collapses in complexity theory occur. We then study the relation between safe approximation and kernelization. We demonstrate how the notion of safe approximation can be useful in designing kernelization algorithms for certain fixed-parameter tractable problems. On the other hand, we show that there are problems that have constant-ratio safe approximation algorithms but no polynomial kernels, unless the polynomial hierarchy collapses to the third level.