Direkt zum Inhalt

Lexikon der Mathematik: Null-Eins-Programmierung

bezeichnet spezielle kombinatorische Optimierungsaufgaben.

Dabei werden für einen Teil der Variablen (oder alle Variablen) nur Belegungen aus der Menge {0, 1} erlaubt. Diese Einschränkung kann enormen Einfluß auf die Schwierigkeit einer algorithmischen Lösung haben. So ist beispielsweise die lineare Programmierung im Turingmodell in polynomialer Zeit lösbar, wogegen die gleiche Fragestellung für Lö-sungen in der Menge {0, 1} NP-vollständig (und damit vermutlich schwieriger) ist.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos