Computer Science & Electrical

Computer Science & Electrical

Archive
Join as an Editor/Reviewer

Enhancement of Irving’s Algorithm with Autocomplete Feature

Volume: 99  ,  Issue: 1 , April    Published Date: 19 April 2022
Publisher Name: IJRP
Views: 100  ,  Download: 39 , Pages: 77 - 86    
DOI: 10.47119/IJRP100981420223061

Authors

# Author Name
1 Karen Claire Morfe
2 Ulysis Agustin
3 Mark Christopher Blanco
4 Dan Michael Cortez
5 Antolin Alipio

Abstract

Irving’s algorithm is the solution Robert W. Irving proposed to Gale and Shapley’s Stable Roommate problem. It determines if there is a possible stable match in each set using a list of preferences, and if it is possible, finds the stable matches. However, incomplete preference lists would increase the chances of having one participant become unmatched. This paper introduces an enhanced version of this algorithm that uses the addition of descriptive lists to fill in the vacancies in the incomplete preference list. The conclusion is that it is more efficient to fill the vacancies according to approximate preference rather than leaving the lists as incomplete to create more stable matches.

Keywords

  • Irving's algorithm
  • Matching
  • Stable Roommates