Bessere Flachbildschirme durch Diskrete Optimierung
Zusammenfassung der Projektergebnisse
In diesem Projekt wurden die algorithmischen Grundlagen zur Ansteuerung von Matrixdisplays untersucht. Aus kombinatorischer Sicht geht es dabei darum, die Kantenmenge eines bipartiten Graphen in möglichst wenige vollständige bipartite Teilgraphen, auch Bicliquen genannt, zu zerlegen. Je nach Bildschirmtechnologie kann dies mit oder ohne Überlappung erfolgen. Wir sprechen dann im ersten Fall von BicliqueCover und im zweiten Fall von BicliquePartition. Es war schon vor Projektbeginn bekannt, dass die beiden Probleme NP-schwer und auch schwer zu approximieren sind. Es gab aber große Lücken zwischen den damals bekannten oberen und unteren Schranken. Es gelang uns im Rahmen dieses Projekts signifikante Fortschritte in Bezug auf die Grenzen der Approximierbarkeit beider Probleme zu erzielen und die Lücken fast zu schließen. Insbesondere konnten wir zeigen, dass die beiden Bicliquenzerlegungsprobleme in einer Liga mit den notorisch schweren kombinatorischen Optimierungsproblemen Clique, Independent Set und Coloring spielen. Die gleichen unteren Schranken für die Approximierbarkeit konnten wir für die verwandten Probleme Max-WeightedBiclique mit Gewichten in {0, 1} und für die Approximation der fraktionalen Bicliquenüberdeckungszahl folgern. Obwohl die genannten Resultate nicht mehr viel Raum für die Verbesserung der trivialen linearen oberen Schranke ließ, konnten wir dennoch die ersten nicht trivialen Approximationsfaktoren für BicliqueCover und BicliquePartition zeigen und einen log-Faktor herausschlagen. Für das Problem, die größte Clique in einem regulären Graphen zu finden, konnten wir ebenfalls die untere Schranke für die Approximierbarkeit signifikant verbessern. Im Gegensatz zu Clique sieht die Lage bei BicliqueCover und BicliquePartition in Bezug auf die parametrisierten Komplexität allerdings besser aus. Es war vor diesem Projekt schon bekannt, dass beide Bicliquenzerlegungsprobleme in FPT sind, jedoch waren die damals besten bekannten Laufzeiten doppelt exponentiell in der Anzahl der Bicliquen in einer optimalen Zerlegung. Für BicliquePartition konnten wir einen Algorithmus entwerfen, dessen Laufzeit signifikant besser in diesem Parameter skaliert. Andererseits konnten wir zeigen, dass BicliqueCover wesentlich schwieriger zu sein scheint, d.h. eine signifikante Verbesserung der doppelt exponentiellen Laufzeit würde bedeuten, dass eine anerkannte Komplexitätshypothese (ETH) falsch wäre. Außerdem zeigten wir exponentielle untere Schranken für Problemkerne für BicliqueCover unter der Annahme, dass P ungleich NP ist. Zusammenfassend lässt sich sagen, dass die theoretischen Resultate dieses Projekts, die überwiegende unteren Schranken verschärften und somit aufzeigten, dass BicliqueCover und BicliquePartition wesentlich schwieriger als vorher angenommen sind und wenig Hoffnung auf effiziente Algorithmen mit unmittelbarer industrieller Verwertbarkeit im Bereich der Adressierung von Matrixdisplays lassen. Dennoch liefern die gefundenen theoretischen Resultate einen wichtigen wissenschaftlichen Beitrag, da der Stand der Forschung insbesondere in Bezug auf die Grenzen der Approximierbarkeit von Bicliquenzerlegungsproblemen signifikant vorangebracht wurde und diese Optimierungsprobleme auch in vielen anderen Bereichen (wie z.B. Bioinformatik, Datenbanken, IT-Sicherheit und Graphenzeichnen) relevant sind.
Projektbezogene Publikationen (Auswahl)
-
“Nearly Tight Approximability Results for Minimum Biclique Cover and Partition,” in Algorithms - ESA 2014 (A. Schulz and D. Wagner, eds.), vol. 8737 of Lecture Notes in Computer Science, pp. 235–246, Springer Berlin Heidelberg, 2014
P. Chalermsook, S. Heydrich, E. Holm, and A. Karrenbauer
-
Cliques in Regular Graphs and the Core- Periphery Problem in Social Networks, COCOA 2016: Combinatorial Optimization and Applications, pp. 175–186, Springer International Publishing, 2016
U. Brandes, E. Holm, and A. Karrenbauer
-
“On the Parameterized Complexity of Biclique Cover and Partition,” in 11th International Symposium on Parameterized and Exact Computation (IPEC 2016) (J. Guo and D. Hermelin, eds.), vol. 63 of Leibniz International Proceedings in Informatics (LIPIcs), (Dagstuhl, Germany), pp. 11:1–11:13, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017
S. Chandran, D. Issac, and A. Karrenbauer
-
Optimierungsprobleme mit Cliquen und Bicliquen in Graphen. Dissertation, Universität Konstanz, Konstanz, 2018
E. Holm
