Effiziente Vorverarbeitung für schwere Probleme: neue Techniken und präzise Modelle für Datenreduktion
Zusammenfassung der Projektergebnisse
Ausgehend vom Begriff der polynomiellen Kernelisierung als Modell für effiziente Vorverarbeitung für schwere Probleme wurden in PREMOD eine Vielzahl von restriktiveren bzw. allgemeineren Modellen sowie zugehörige Techniken für obere und untere Schranken untersucht. Motiviert durch sowohl praktische als auch theoretische Überlegungen und Fragestellungen konnte so ein substanzieller Beitrag zu den Grundlagen effizienter Vorverarbeitung geleistet werden. An neuen Modellen sind insbesondere die ersten Kernelisierungen mit lediglich logarithmischem Speicher bzw. in Form von Streamingalgorithmen zu erwähnen. Auch wurde mit “preprocessing under uncertainty” eine neuartige Fragestellung zur Vorverarbeitung für effizient lösbare Probleme eingeführt und untersucht. Motiviert durch eine Frage von Lokshtanov et al. zu approximativer Kernelisierung wurden im Projekt die ersten nicht-trivialen approximativen Turingkernelisierungen entwickelt. Als weitere neue Technik sei auch die untere Schranke für Vorverarbeitung des Point Line Cover Problems erwähnt, bei der die volle Stärke der “oracle communication protocols” von Dell und van Melkebeek eingesetzt werden konnte. Des Weiteren wurden viele neue Resultate zu aktuellen Fragestellungen im Bereich Kernelisierung gewonnen. Darunter eine Vielzahl an Resultaten zu bestmöglichen Parametern für Vertex Cover, die eine polynomielle Kernelisierung erlauben, sowie deren Charakterisierung. Ebenso neue Resultate zu matroid-basierten Kernelisierungen, aufbauend auf Arbeiten von Kratsch und Wahlström. Nicht zuletzt konnten viele Erkenntnisse zur Kernelisierbarkeit von Problemen auf ganzzahligen linearen Programmen gewonnen werden.
Projektbezogene Publikationen (Auswahl)
- On Polynomial Kernels for Integer Linear Programs: Covering, Packing and Feasibility. ESA 2013: 647-658
Stefan Kratsch
(Siehe online unter https://doi.org/10.1007/978-3-642-40450-4_55) - Streaming Kernelization. MFCS (2) 2014: 275-286
Stefan Fafianie, Stefan Kratsch
(Siehe online unter https://doi.org/10.1007/978-3-662-44465-8_24) - A Structural Approach to Kernels for ILPs: Treewidth and Total Unimodularity. ESA 2015: 779-791
Bart M. P. Jansen, Stefan Kratsch
(Siehe online unter https://doi.org/10.1007/978-3-662-48350-3_65) - A Randomized Polynomial Kernel for Subset Feedback Vertex Set. Theory Comput. Syst. 62(1): 63-92 (2018)
Eva-Maria C. Hols, Stefan Kratsch
(Siehe online unter https://doi.org/10.1007/s00224-017-9805-6) - Point Line Cover: The Easy Kernel is Essentially Tight. ACM Trans. Algorithms 12(3): 40:1-40:16 (2016)
Stefan Kratsch, Geevarghese Philip, Saurabh Ray
(Siehe online unter https://doi.org/10.1145/2832912) - Preprocessing Under Uncertainty. STACS 2016: 33:1-33:13
Stefan Fafianie, Stefan Kratsch, Vuong Anh Quyen
(Siehe online unter https://doi.org/10.4230/LIPIcs.STACS.2016.33) - A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter. SIAM J. Discret. Math. 32(3): 1806-1839 (2018)
Stefan Kratsch
(Siehe online unter https://doi.org/10.1137/16M1104585) - On Kernelization for Edge Dominating Set under Structural Parameters. STACS 2019: 36:1-36:18
Eva-Maria C. Hols, Stefan Kratsch
(Siehe online unter https://doi.org/10.4230/LIPIcs.STACS.2019.36) - Approximate Turing Kernelization for Problems Parameterized by Treewidth. ESA 2020: 60:1-60:23
Eva-Maria C. Hols, Stefan Kratsch, Astrid Pieterse
(Siehe online unter https://doi.org/10.4230/LIPIcs.ESA.2020.60) - Elimination Distances, Blocking Sets, and Kernels for Vertex Cover. STACS 2020: 36:1-36:14
Eva-Maria C. Hols, Stefan Kratsch, Astrid Pieterse
(Siehe online unter https://doi.org/10.4230/LIPIcs.STACS.2020.36)
