q aosr/3i8k8
Was ist die Idee bei einem LP?
? aosr/3i8k8/m/1bsv
q aosr/7ah83
Kann ein LP in poly Zeit gelöst werden?
? aosr/7ah83/m/69kv
Ja
q aosr/ufpi9
Kann ein ILP in poly Zeit gelöst werden?
? aosr/ufpi9/m/2shk
allgemein Nein,
aber man kann manche ILPs als LPs darstellen, wenn alle optimalen Lösungen des LP auch Integer sind.
ILPs können NP schwere Probleme darstellen
q aosr/4vbg4
Wie arbeitet der Simplex LP solver?
? aosr/4vbg4/m/6teb
q aosr/6vm3r
Wie funktioniert der Ellipsoid method LP slover?
? aosr/6vm3r/m/1v59
q aosr/5lqlf
Was hat ein polyhedron, point separation problem mit LP zu tun?
? aosr/5lqlf/m/283d
q aosr/gk1pe
Wie funktioniert LP relaxations?
? aosr/gk1pe/m/76rt
q aosr/7b38j
Wie errechnet man ein Dual LP?
? aosr/7b38j/m/24n6
q aosr/for8d
Was ist Weak Duality?
? aosr/for8d/m/45l1
q aosr/766o1
Was ist Strong Duality?
? aosr/766o1/m/61ca
q aosr/6lc0f
Was ist “Complementary Slackness”?
? aosr/6lc0f/m/66b0
q aosr/1ajp0
Was ist eine Totally Unimodular Matrices?
? aosr/1ajp0/m/6pjn
q aosr/7uivm
Wie kann man eine Totally Unimodular Matrices in LPs verwenden?
? aosr/7uivm/m/6ovm
q aosr/73mbm
Ist die Incident Matrix von einem Graph immer eine Totally Unimodular Matrices?
? aosr/73mbm/m/6m49
Nur wenn der graph bipartite ist oder directed.