Strukturparameter in der Ganzzahligen Programmierung

• Antragsteller: Professor Dr.-Ing. Kim-Manuel Klein
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2025
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 562801570

Im Rahmen des Projektes betrachten wir ganzzahlig lineare Programme (ILPs) der Form {x \in Z^n | Ax = b, x >= 0}. Sehr viele klassische algorithmische Probleme lassen sich einfach als ein derartiges ILP formulieren - beispielsweise das klassische Teilsummenproblem oder das Bin Packing-Problem. Abhängig von dem formulierten Problem hat das entsprechende ILP dabei in der Regel eine sehr spezielle Form. Das Hauptziel des Projektes ist es, die grundlegende strukturelle und geometrische Eigenschaft dieser ILPs zu charakterisieren und besser zu verstehen. Aufbauend auf einer geometrischen Interpretationen dieser ILPs, möchten wir dann Algorithmen zum Lösen der ILPs entwickeln und so effizientere Algorithmen für algorithmische Problemstellungen finden. Ein wichtiges Ziel des Antrages ist es, ein Algorithmus zum Lösen von ILPs mit einer Laufzeit von f(\Delta) poly(|I|) zu entwickeln, wobei \Delta der Betrag der größten Unterdeterminate der Constraint-Matrix ist. Unser Ansatz basiert dabei auf einer Dichotomieaussage von Zulässigkeits-ILPs, welche wir ebenfalls genauer untersuchen möchten.

• DFG-Verfahren: Sachbeihilfen