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