Kernelisierung für große Datenmengen
Zusammenfassung der Projektergebnisse
Das Verfahren der Kernelisierung bezeichnet den Prozess, große Datenmengen effizient zu verkleinern, und zwar dergestalt, dass dabei eine optimale Lösung eines fest gewählten Optimierungsproblems erhalten bleibt. Durch den Prozess der Kernelisierung können schwierige Optimierungsprobleme auf großen Datenmengen optimal gelöst werden, da teure Rechenoperationen nur auf der reduzierten Datenmenge (dem sogenannten Kern) ausgeführt werden müssen. Forschung zur Kernelisierung beschäftigt sich somit damit, Regeln zu entwickeln, die möglichst effizient und gleichzeitig effektiv zu Reduktionen führen. In der Praxis werden solche Regeln seit etwa den 1960er Jahren angewandt, im Kontext der systematischen Entwicklung von Programmcode zur Lösung komplexer ingenieur- und wirtschaftswissenschaftlicher Fragestellungen auf großen Datenmengen, wobei „groß“ stets relativ zur verfügbaren Hardwareleistung (üblicherweise gemessen in FLOPS oder bytes) zu sehen ist. Die seit Anfang der 1990er Jahre entwickelte Parameterisierte Komplexitätstheorie erlaubte dann erstmals, theoretische Aussagen über die Effektivität solcher Regeln zu argumentieren, die insbesondere in der Größe des Kerns gemessen wird. Diese Kerngröße wird üblicherweise relativ zu einem sogenannten Parameter gemessen, wie beispielsweise dem Optimalwert des Optimierungsproblems, von dem bekannt ist, dass dieser „klein“ relativ zur Größe der gesamten Datenmenge verhält. Seit Anfang der 2000er Jahre erlebt die Theorie der Kernelisierung ein noch stets anhaltendes exponentielles Wachstum, welches sich insbesondere in zahlreichen Kernen von Größe polynomiell im Parameter, oder Beweisen der Nichtexistenz kleiner Kerne (modulo verschiedener komplexitätstheoretischer Hypothesen), ausdrückt. Der Fokus lag jedoch vor allem auf der Kerngröße, nicht so sehr auf der Effizienz der Implementierung der Reduktionsregeln, und war vor allem theoretischer Natur. In diesem Projekt sollten neue Reduktionsregeln erforscht werden, die sowohl effektiv als auch effizient sind. Dies gelang in mehrerlei Hinsicht. Zum einen konnten Kerngröße und Laufzeiten von Reduktionsregeln deutlich reduziert werden, z.B. für das fundamentale Max-Cut-Problem mit Parameter dem Gewinn über der bekannten Edwards-Erdős-Schranke. Hierfür zeigten wir einen Kern linearer Größe (was theoretisch optimal ist), und wie man diesen Kern in linearer Zeit erreicht (was ebenso theoretisch optimal ist). Diese theoretische Arbeit wurde dann in einer Masterarbeit in einen Kernelisierungsalgorithmus umgesetzt, der von hoher Praxisrelevanz ist: mit ihm konnten zahlreiche Benchmark-Instanzen optimal gelöst werden, deren Optimallösungen viele Jahre offengeblieben waren. Andere Instanzen konnten wir mit unserer Implementierung mehr als 100 Mal schneller lösen als es über Jahre dezidiert entwickelte Solver konnten. Dieses für uns überraschende Ergebnis hat uns sehr erfreut, ebenso wie die Tatsache, dass diese Arbeit mit dem Preis des DFG-Schwerpunktprogramms 1736 „Algorithms for Big Data“ 2019 ausgezeichnet wurde. Neben dem klassischen Max-Cut-Problem auf ungerichteten Graphen haben wir uns auch mit Kernelisierung für gerichtete Graphen beschäftigt, was aufgrund mangelnder Standardtechniken als unterentwickeltes Feld bezeichnet werden kann. Hier konnten wir Fortschritte erzielen für das gerichtete Feedback Vertex Set-Problem, für das die Existenz eines kleinen (polynomiell großen) Kerns eines der bekanntesten offenen Probleme der Kernelisierung überhaupt ist. Unser Fortschritt beruht auf der neuen Idee, den Ausgabegraphen zu beschränken, im Gegensatz zur vorher üblichen Beschränkung des Eingabegraphen. Überdies machten wir das Werkzeug der gleichzeitigen diophantischen Approximation aus dem Operations Research in der Kernelisierungsforschung bekannt. Dadurch konnten wir eine bekannte offene Frage aus einem Kompendium des Forschungsgebietes lösen, und das weite Gebiet der Optimierungsprobleme auf gewichteten Instanzen für die Kernelisierung erschließen. Schließlich beschäftigten wir uns mit Kernelisierungsregeln für dynamische Probleme, und entwickelten hier zwei neue Modelle. Erstmals zeigten wir untere Schranken für Kerngrößen dynamischer Optimierungsprobleme. Unsere Modelle und Algorithmen wurden bereits von mehreren Folgearbeiten aufgegriffen. Zusammenfassend konnten wir im Projekt die Kernelisierung in verschiedene Richtungen vorantreiben, und ihre Anwendbarkeit deutlich erweitern.
Projektbezogene Publikationen (Auswahl)
- Parameterized algorithms for generalizations of directed feedback vertex set. Proc. CIAC 2019, pp. 249-261, 2019
A. Göke, D. Marx, M. Mnich
(Siehe online unter https://doi.org/10.1007/978-3-030-17402-6_21) - Resolving infeasibility of linear systems: A parameterized approach. Proc. IPEC 2019, 17:1-17:15, 2019
A. Göke, L. M. Mendoza Cadena, M. Mnich
(Siehe online unter https://doi.org/10.4230/LIPIcs.IPEC.2019.17) - Dynamic parameterized problems and algorithms. ACM Trans. Algorithms 16(4): 45:1-45:46, 2020
J. Alman, M. Mnich, V. Vassilevska Williams
(Siehe online unter https://doi.org/10.1145/3395037) - Engineering kernelization for maximum cut. Proc. ALENEX 2020, pp. 27-41, 2020
D. Ferizovic, D. Hespe, S. Lamm, M. Mnich, Ch. Schulz, D. Strash
(Siehe online unter https://doi.org/10.1137/1.9781611976007.3) - Hitting long directed cycles is fixed-parameter tractable. Proc. ICALP 2020, Leibniz International Proceedings in Informatics 168, pp. 59:1-59:18, 2020
A. Göke, D. Marx, M. Mnich
(Siehe online unter https://doi.org/10.1137/1.9781611975994.56) - Odd multiway cut in directed acyclic graphs. SIAM J. Discrete Math. 34(2), pp. 1385-1408, 2020
K. Chandrasekaran, M. Mnich, S. Mozzafari
(Siehe online unter https://doi.org/10.1137/18m1176087) - Recent advances in practical data reduction. Technischer Bericht
F. Abu-Khzam, S. Lamm, M. Mnich, A. Noe, Ch. Schulz, D. Strash
(Siehe online unter https://doi.org/10.48550/arXiv.2012.12594) - Solving packing problems with few small items using rainbow matchings. Proc. MFCS 2020, Leibniz International Proceedings in Informatics 170, pp. 11:1-11:14, 2020
M. Bannach, S. Berndt, M. Maack, M. Mnich, A. Lassota, M. Rau, M. Skambath
(Siehe online unter https://doi.org/10.1155/2020/3050714)
