nobody
08.07.2003, 10:33
Hallo,
die Ellipsoid-Methode war das erste polynomiale Verfahren für lineare Programmierungsprobleme.
Ich habe ein paar Probleme mit der Aufwandsabschätzung:
Die Initialisierung
(a) k:=1;
(b) N:= 2n( (2n+1) \C\ + n \b\ -n^3);
(c) A0:= R^2I mit R:= n^(1/2) 2^(\C,b\ -n^2);
(d) a0:= 0;
(k Index, N maximale Zahl der Iterationen, n Anzahl Entscheidungsvariablen, C mxn-Matrix, \ \ Codierungslänge, A0 die die Form des Ellipsoids festlegende Matrix, a0 Mittelpunkt des Ellipsoids, R Startradius, I Einheitsmatrix)
soll laut einer Quelle O(n^2), laut einer anderen O(m*n) Elementarschritte benötigen. Was davon ist richtig und wieso? Auch habe ich Schwierigkeiten mit \C,b\, der Codierungslänge von C und b. Ist das die Anzahl der binären Stellen, die zur Repräsentation von C und b (im Sinne einer Summe) nötig sind?? (Ein kleines Bsp. hierzu würde mir weiterhelfen)
Ich tippe auf O(n*m), da für jeden Eintrag der nxm-Matrix C die Codierungslänge berechnet werden muss... Also wäre O(n^2) falsch, da m>=n.
Schöne Grüße und vielen Dank,
Martin
die Ellipsoid-Methode war das erste polynomiale Verfahren für lineare Programmierungsprobleme.
Ich habe ein paar Probleme mit der Aufwandsabschätzung:
Die Initialisierung
(a) k:=1;
(b) N:= 2n( (2n+1) \C\ + n \b\ -n^3);
(c) A0:= R^2I mit R:= n^(1/2) 2^(\C,b\ -n^2);
(d) a0:= 0;
(k Index, N maximale Zahl der Iterationen, n Anzahl Entscheidungsvariablen, C mxn-Matrix, \ \ Codierungslänge, A0 die die Form des Ellipsoids festlegende Matrix, a0 Mittelpunkt des Ellipsoids, R Startradius, I Einheitsmatrix)
soll laut einer Quelle O(n^2), laut einer anderen O(m*n) Elementarschritte benötigen. Was davon ist richtig und wieso? Auch habe ich Schwierigkeiten mit \C,b\, der Codierungslänge von C und b. Ist das die Anzahl der binären Stellen, die zur Repräsentation von C und b (im Sinne einer Summe) nötig sind?? (Ein kleines Bsp. hierzu würde mir weiterhelfen)
Ich tippe auf O(n*m), da für jeden Eintrag der nxm-Matrix C die Codierungslänge berechnet werden muss... Also wäre O(n^2) falsch, da m>=n.
Schöne Grüße und vielen Dank,
Martin