q aosr/4t45n
Was ist ein perfektes Matching?
? aosr/4t45n/m/53kl
q aosr/10k1u
Was ist der Heiratssatz?
? aosr/10k1u/m/1jta
Es muss immer mindestens viele Nachbarn geben für jedes geben.
q aosr/3mlnm
Wie errechnet man ein Maximum-weight bipartite matching?
? aosr/3mlnm/m/3iqd
shortest -> Lowest sum of weights
Was ist ein extreme Matching?
?
q aosr/7ftkj
Wie kann man das Minimum-cost bipartite matching errechnen?
? aosr/7ftkj/m/ko43
is basically the Maximum-weight bipartite matching with inverted weights.
Proof: Advanced Algorithms UE 1.3
q aosr/17skd
Was ist die Laufzeit eines Maximum-weight bipartite matching?
? aosr/17skd/m/edf4
q aosr/5k6aq
Was ist ein Stable Matchings?
? aosr/5k6aq/m/t9ho
Es gibt keine Kante wo beide sich gegenseitig lieber möchten als ihren aktuellen partner.
q aosr/tgfc8
Gib es immer ein stable Matching?
? aosr/tgfc8/m/7bll
Ja in bipartite Graphs
q aosr/12css
Kann ein stable Matching in poly Zeit errechnet werden?
? aosr/12css/m/qd7s
Ja für bipartite Graphs
q aosr/6u3jd
Gibt es immer ein bestes stable Matching?
? aosr/6u3jd/m/1l96
Nein, es hängt ab für wenn es am besten sein soll.
q aosr/6olo2
Was ist das Stable marriage problem?
? aosr/6olo2/m/5nfb
Ein Stable Matchings in einem Bipatiter Graph
q aosr/3t7to
Welche möglichkeiten gibt es das Stable marriage problem zu lösen?
? aosr/3t7to/m/7n44
Approach 1: Enumeration
Approach 2: Greedy
3rd Approach: Gale-Shapley Algorithm
q aosr/4ujm0
Wie funktioniert der Gale-Shapley Algorithm?
? aosr/4ujm0/m/15o5
q aosr/1vug3
Was ist die Laufzeit vom Gale-Shapley Algorithm?
? aosr/1vug3/m/24bh
q aosr/29nbh
Warum ist der Gale-Shapley Algorithm Man optimal?
? aosr/29nbh/m/3gld
q aosr/3fi9g
Warum findet der Gale-Shapley Algorithm das schlimmste mögliche matching für die Frauen?
? aosr/3fi9g/m/6bi8
q aosr/15eit
Kann der Gale-Shapley Algorithm manipuliert werden?
? aosr/15eit/m/3im5
