Tanzpartner finden

Für einen Paartanzabend sollen Tanzpaare gebildet werden. Dafür gibt es $n$ Führende (früher: "Männerpart") und $n$ Folgende (früher: Frauenrolle). Außerdem gibt es für jedes mögliche Tanzpaar einen Wert, wie gut beide miteinander tanzen können (höher ist besser, alle Tanzwerte sind unterschiedlich).
Aufgabe: Bilde Tanzpaare so dass die Summe der Tanzwerte maximiert wird. (Jede Tanzende darf nur in maximal einem Paar vorkommen.)
Idee 1: Nimm das Paar mit dem besten Tanzwert. Entferne beide Tanzenden aus der Instanz und iteriere.
Idee 2: Verbiete dem Paar mit dem geringsten Tanzwert, miteinander zu tanzen. Iteriere diese Verbote so lange, bis jeder Tanzende nur noch höchstens ein erlaubtes Paar bilden kann.

Zeige, dass beide Ideen im Allgemeinen nicht ein Optimum finden.