

![0_image_0.png](0_image_0.png) 

![0_image_1.png](0_image_1.png) 

problems of size 10, fixing p1 to 0.5 and varying p2 in [0,1]. We did the same experiments (generating new instances), and obtained stable marriages of a very similar size to those reported in [4]. This means that although our algorithm is incomplete in principle, it always finds an optimal solution in our randomly generated instances, and for small sizes it behaves as a complete algorithm in terms of size of the returned marriage. However, we can also tackle problems of much larger sizes (at least 100), still obtaining optimal solutions most of the times.

We also considered the runtime behavior of our algorithm. In Figure 5 we show the average normalized number of blocking pairs and, in Figure 6, the average normalized number singles of the best marriage as the execution proceeds.

Although the step limit is 50000, we only plot results for the first steps because the rest is a long plateau that is not very interesting. We shows the results only for p2 = 0.5. However, for greater (resp., lower) number of ties the curves