An efficient algorithm to find a maximum weakly stable matching for SPA-ST problem
Tác giả: Nguyễn Thị Uyên, Trần Xuân Sang
21st International Conference on Artificial Intelligence and Soft Computing
Quyển: 13589 Trang: 356–366
Năm xuất bản: 1/2023
Tóm tắt
This paper presents a heuristic algorithm to seek a maximum weakly stable matching for the Student-Project Allocation with lecturer preferences over Students containing Ties (SPA-ST) problem. We extend Gale-Shapley’s idea to find a stable matching and propose two new heuristic search strategies to improve the found stable matching in terms of maximum size. The experimental results show that our algorithm is more effective than AP in terms of solution quality and execution time for solving the MAX-SPA-ST problem of large sizes.
Từ khóa
SPA · Heuristic Search · Weakly Stable Matching · MAXSPA-ST · Undominated Blocking Pairs.
