An approximate search algorithm for the student-internship allocation problem

Abstract

This paper proposes an approximate search algorithm to solve the student-internship allocation problem. The key idea of the algorithm is that in each iteration, each student unassigned to an enterprise will be assigned to an enterprise where the student ranks it highest, and it remains at maximum capacity. If the enterprise assigned to the student overcomes its capacity, then the enterprise will remove a student to whom it ranks the worst student to allow it not to overcome its capacity. Experimental results with randomly generated datasets show that our algorithm is efficient for the problem of large sizes.

Keywords

• blocking pair
• stable matching
• internship allocation
• approximation algorithm