Ant colony B ased algorithm for stable marriage problem

Ngo Anh Vien, Nguyen Hoang Viet, Hyun Kim, Seung Gwan Lee, Tae Choong Chung*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Citations (Scopus)

Abstract

This paper introduces ant colony system (ACS), a distributed algorithm that is applied to the Stable Marriage Problem (SM). The stable marriage problem is an extensivelystudied combinatorial problem with many practical applications. It is well known that at least one stable matching exists for every stable marriage instance. However, the classical Gale-Shapley [2] algorithm produces a marriage that greatly favors the men at the expense of the women, or vice versa. In our proposed ACS, a set of cooperating agents called ants cooperate to find stable matchings such as stable matching with man-optimal, womanoptimal, egalitarian stable matching, sex-fair stable matching. So this ACS is a novel method to solve Stable Marriage Problem. Our simulation results show the effectiveness of the proposed ACS.

Original languageEnglish
Title of host publicationAdvances and Innovations in Systems, Computing Sciences and Software Engineering
Pages457-461
Number of pages5
DOIs
Publication statusPublished - 01 Dec 2007
Externally publishedYes
Event2006 International Conference on Systems, Computing Sciences and Software Engineering, SCSS 2006, Part of the International Joint Conferences on Computer, Information, and Systems Sciences, and Engineering, CISSE 2006 -
Duration: 04 Dec 200614 Dec 2006

Conference

Conference2006 International Conference on Systems, Computing Sciences and Software Engineering, SCSS 2006, Part of the International Joint Conferences on Computer, Information, and Systems Sciences, and Engineering, CISSE 2006
Period04/12/200614/12/2006

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Ant colony B ased algorithm for stable marriage problem'. Together they form a unique fingerprint.

Cite this