Record #361631 - GSI Repository

DFG project G:(GEPRIS)562801570

Strukturparameter in der Ganzzahligen Programmierung

Coordinator	Professor Dr.-Ing. Kim-Manuel Klein
Grant period	2025 -
Funding body	Deutsche Forschungsgemeinschaft
	DFG
Identifier	G:(GEPRIS)562801570

Note: 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.

Recent Publications

There are no publications

Record created 2025-08-26, last modified 2025-08-26

Similar records

Add to personal basket
Export as Author List with IDs BibTeX (UTF-8), EndNote XML, EndNote Text, RIS, MARC, Print MARC, MARCXML, DC,
Request correction
Submit fulltext

GSI Homepage \| GSI Library \| English Deutsch \| guest :: login GSI Repository
Search	Submit	Personalize Your alerts Your baskets Your searches	Help