Algorithm Engineering für MONET und verwandte Abdeckungsprobleme

• Applicant: Professor Dr. Martin Mundhenk
• Subject Area: Theoretical Computer Science
• Term: from 2009 to 2013
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 149546573

Der Äquivalenztest monotoner Boolescher Formeln in Normalform (Problem MONET) findet sich in vielen wichtigen Problemstellungen aus den unterschiedlichsten Bereichen der Informatik wieder. Es gibt sehr unterschiedliche Algorithmen für MONET, aber keiner davon hat polynomielle Rechenzeit. Ungeklärt ist, ob nur die bekannten Algorithmen nicht gut genug sind, oder ob es für MONET keinen schnellen Algorithmus geben kann. Umso interessanter und von praktischer Bedeutung ist damit die Frage, welcher der bekannten Algorithmen für welche Anwendungen am schnellsten ist. Im beantragten Projekt soll eine auf Experimenten basierende Studie einen Vergleich von sorgfältigen Implementierungen der bekannten Algorithmen ermöglichen. Hierzu suchen wir für jeden Algorithmus besonders schwer zu behandelnde Probleminstanzen. Diese Instanzen werden Teil einer im Zuge des Projektes zu erstellenden Online-MONET-Instanzen-Bibliothek. Schließlich soll experimentell untersucht werden, welche Modifikationen die bekannten Algorithmen verbessern. Die bisher kaum untersuchte Multiplikationsmethode bietet sich wegen ihrer Freiheitsgrade ganz besonders für eine Untersuchung mittels Algorithm Engineering an.

• DFG Programme: Priority Programmes
• Subproject of: SPP 1307: Algorithm Engineering