Ellipsoidmethode Iterationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 17:20 Do 16.06.2011 | | Autor: | tobster |
| Aufgabe | Sei P = P(A,b) ein Polytop mit einer ganzzahligen Matrix A und einem ganzzahligen Vektor b. Es gelte Vol(P) [mm] \not= [/mm] 0.
Wieviele Iterationen benötigt die Ellipsoidmethode höchstens, um einen Punkt in P zu identifzieren? |
Hallo,
habe leider irgendwie keinen Ansatz für diese Aufgabe mit der Ellipsoidmethode...
Ich weiß, dass für Vol(P) [mm] \not= [/mm] 0 gilt
Vol (P(A,b)) > [mm] \bruch{1}{2^{(n+1)n(\gamma +log n)}}
[/mm]
Als Anfang können wir für die Methode laut Vorlesung dann nehmen:
E0 = [mm] \wurzel{n} 2^{n(\gamma +log n)}
[/mm]
Die Ellipsoidmethode läuft ja solange bis
vol (Ek) [mm] \le \bruch{1}{2^{(n+1)n(\gamma +log n)}}
[/mm]
Aber wie soll ich die Anzahl Iterationen bestimmen können ohne Angabe, was A und b ist?
Kann mir jemand einen Tipp geben?
Danke und viele Grüße
Tobster
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:20 Sa 18.06.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
