Egészszámú programozási feladatok néhány transzformációja

Absztrakt

Ennek a dolgozatnak az első részében megadunk egy olyan transzformációt (helyesebben 11 transzformációk egy sorozatát), mely tetszőleges nulla-egy kvadratikus programozási feladatot (IQP) úgy transzformál HL, HF, HK, CK, EL feladatokká, hogy ezen problémák együtthatómátrixa csupán az eredeti IQP változóinak számától, n-től függ. Pontosabban: a HL, HF, HK, UK, EL problémák feltételeinek és változóinak száma n² nagyságrendű (0(n²)).
A második részben arra adunk egy módszert, hogy hogyan lehet egy IQP-t fix-költséges szállítási feladattá (FK) transzformálni. Az FK költségmátrixa n + 1-rendű.