AN EFFICIENT DEPTH-FIRST SEARCH ALGORITHM FOR SOLVING THE MAXIMUM STABLE MARRIAGE PROBLEM WITH TIES AND INCOMPLETE LISTS

Abstract

This paper proposes an efficient depth-first search algorithm to solve the maximum stable marriage problem with ties and incomplete preference lists. The key idea of the algorithm is to initialize an empty matching and mark all men as unmatched. In each iteration, an unmatched man proposes to the most preferred woman on his rank list. If the woman is unmatched or prefers the proposing man over her current partner, she is assigned to the man, forming a new pair in the matching. Otherwise, she keeps her current partner and rejects the proposing man. When a man is rejected by a woman, he becomes unmatched. The algorithm then recursively processes the next unmatched man until it either finds a complete matching or reaches a predefined maximum number of iterations. Experimental results on randomly generated datasets show that our algorithm is effective in producing high- quality solutions to the problem.

Keywords

• depth-first search
• gale-shapley algorithm
• stable matching
• stable marriage problem
• ties and incomplete lists