Ant colony B ased algorithm for stable marriage problem

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

doi:10.1007/978-1-4020-6264-3_79

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 proceeding › Conference 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 language	English
Title of host publication	Advances and Innovations in Systems, Computing Sciences and Software Engineering
Pages	457-461
Number of pages	5
DOIs	https://doi.org/10.1007/978-1-4020-6264-3_79
Publication status	Published - 01 Dec 2007
Externally published	Yes
Event	2006 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 2006 → 14 Dec 2006

Conference

Conference	2006 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
Period	04/12/2006 → 14/12/2006

ASJC Scopus subject areas

Software

Access to Document

10.1007/978-1-4020-6264-3_79

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

Cite this

@inproceedings{34bb68f5b82f42efb1c99288f56ba65a,

title = "Ant colony B ased algorithm for stable marriage problem",

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.",

author = "Vien, {Ngo Anh} and Viet, {Nguyen Hoang} and Hyun Kim and Lee, {Seung Gwan} and Chung, {Tae Choong}",

year = "2007",

month = dec,

day = "1",

doi = "10.1007/978-1-4020-6264-3_79",

language = "English",

isbn = "9781402062636",

pages = "457--461",

booktitle = "Advances and Innovations in Systems, Computing Sciences and Software Engineering",

note = "2006 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 ; Conference date: 04-12-2006 Through 14-12-2006",

}

Vien, NA, Viet, NH, Kim, H, Lee, SG & Chung, TC 2007, Ant colony B ased algorithm for stable marriage problem. in Advances and Innovations in Systems, Computing Sciences and Software Engineering. pp. 457-461, 2006 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, 04/12/2006. https://doi.org/10.1007/978-1-4020-6264-3_79

TY - GEN

T1 - Ant colony B ased algorithm for stable marriage problem

AU - Vien, Ngo Anh

AU - Viet, Nguyen Hoang

AU - Kim, Hyun

AU - Lee, Seung Gwan

AU - Chung, Tae Choong

PY - 2007/12/1

Y1 - 2007/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=77955860899&partnerID=8YFLogxK

U2 - 10.1007/978-1-4020-6264-3_79

DO - 10.1007/978-1-4020-6264-3_79

M3 - Conference contribution

AN - SCOPUS:77955860899

SN - 9781402062636

SP - 457

EP - 461

BT - Advances and Innovations in Systems, Computing Sciences and Software Engineering

T2 - 2006 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

Y2 - 4 December 2006 through 14 December 2006

ER -