Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-26018
Titel: Kernelization of generic problems : upper and lower bounds
Verfasser: Kratsch, Stefan
Sprache: Englisch
Erscheinungsjahr: 2010
SWD-Schlagwörter: Kernel <Informatik>
Datenkompression
Prädikatenlogik
Constraint-Erfüllung
Freie Schlagwörter: kernelization
constraint satisfaction problem
DDC-Sachgruppe: 004 Informatik
Dokumentart : Dissertation
Kurzfassung: This thesis addresses the kernelization properties of generic problems, defined via syntactical restrictions or by a problem framework. Polynomial kernelization is a formalization of data reduction, aimed at combinatorially hard problems, which allows a rigorous study of this important and fundamental concept. The thesis is organized into two main parts. In the first part we prove that all problems from two syntactically defined classes of constant-factor approximable problems admit polynomial kernelizations. The problems must be expressible via optimization over first-order formulas with restricted quantification; when relaxing these restrictions we find problems that do not admit polynomial kernelizations. Next, we consider edge modification problems, and we show that they do not generally admit polynomial kernelizations. In the second part we consider three types of Boolean constraint satisfaction problems.We completely characterize whether these problems admit polynomial kernelizations, i.e.,given such a problem our results either provide a polynomial kernelization, or they show that the problem does not admit a polynomial kernelization. These dichotomies are characterized by properties of the permitted constraints.
Diese Dissertation beschäftigt sich mit der Kernelisierbarkeit von generischen Problemen, definiert durch syntaktische Beschränkungen oder als Problemsystem. Polynomielle Kernelisierung ist eine Formalisierung des Konzepts der Datenreduktion für kombinatorisch schwierige Probleme. Sie erlaubt eine grüdliche Untersuchung dieses wichtigen und fundamentalen Begriffs. Die Dissertation gliedert sich in zwei Hauptteile. Im ersten Teil beweisen wir, dass alle Probleme aus zwei syntaktischen Teilklassen der Menge aller konstantfaktor-approximierbaren Probleme polynomielle Kernelisierungen haben. Die Probleme müssen durch Optimierung über Formeln in Prädikatenlogik erster Stufe mit beschränkter Quantifizierung beschreibbar sein. Eine Relaxierung dieser Beschränkungen gestattet bereits Probleme, die keine polynomielle Kernelisierung erlauben. Im Anschluss betrachten wir Kantenmodifizierungsprobleme und zeigen, dass diese im Allgemeinen keine polynomielle Kernelisierung haben. Im zweiten Teil betrachten wir drei Arten von booleschen Constraint-Satisfaction-Problemen. Wir charakterisieren vollständig welche dieser Probleme polynomielle Kernelisierungen erlauben. Für jedes gegebene Problem zeigen unsere Resultate entweder eine polynomielle Kernelisierung oder sie zeigen, dass das Problem keine polynomielle Kernelisierung hat. Die Dichotomien sind durch Eigenschaften der erlaubten Constraints charakterisiert.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-35302
hdl:20.500.11880/26074
http://dx.doi.org/10.22028/D291-26018
Erstgutachter: Mehlhorn, Kurt
Tag der mündlichen Prüfung: 30-Aug-2010
SciDok-Publikation: 21-Jan-2011
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
Fachrichtung: MI - Mathematik
Fakultät / Institution:MI - Fakultät für Mathematik und Informatik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
Dissertation_5566_Krat_Stef_2010.pdf1,09 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.