A Heuristic Repair Algorithm for the Maximum Stable Marriage Problem with Ties and Incomplete Lists

Hoang Huu Viet; Nguyen Thi Uyen; Son Thanh Cao; Tae Choong Chung

doi:10.1007/978-3-030-97546-3_40

A Heuristic Repair Algorithm for the Maximum Stable Marriage Problem with Ties and Incomplete Lists

Hoang Huu Viet
, Nguyen Thi Uyen
, Son Thanh Cao
, Tae Choong Chung

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

This paper proposes a heuristic repair algorithm to find a maximum weakly stable matching for the stable marriage problem with ties and incomplete lists. Our algorithm is designed including a well-known Gale-Shapley algorithm to find a stable matching for the stable marriage problem with ties and incomplete lists and a heuristic repair function to improve the found stable matching in terms of maximum size. Experimental results for large randomly generated instances of the problem showed that our algorithm is efficient in terms of both execution time and solution quality for solving the problem.

Original language	English
Title of host publication	AI 2021
Subtitle of host publication	Advances in Artificial Intelligence - 34th Australasian Joint Conference, AI 2021, Proceedings
Editors	Guodong Long, Xinghuo Yu, Sen Wang
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	494-506
Number of pages	13
ISBN (Print)	9783030975456
DOIs	https://doi.org/10.1007/978-3-030-97546-3_40
Publication status	Published - 2022
Event	34th Australasian Joint Conference on Artificial Intelligence, AI 2021 - Virtual, Online Duration: 2 Feb 2022 → 4 Feb 2022

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13151 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	34th Australasian Joint Conference on Artificial Intelligence, AI 2021
City	Virtual, Online
Period	2/02/22 → 4/02/22

Bibliographical note

Publisher Copyright:
© 2022, Springer Nature Switzerland AG.

Keywords

Gale-Shapley algorithm
Heuristic repair
SMTI
Stable marriage problem

Access to Document

10.1007/978-3-030-97546-3_40

Cite this

Viet, H. H., Uyen, N. T., Cao, S. T., & Chung, T. C. (2022). A Heuristic Repair Algorithm for the Maximum Stable Marriage Problem with Ties and Incomplete Lists. In G. Long, X. Yu, & S. Wang (Eds.), AI 2021: Advances in Artificial Intelligence - 34th Australasian Joint Conference, AI 2021, Proceedings (pp. 494-506). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13151 LNAI). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-030-97546-3_40

Viet, Hoang Huu ; Uyen, Nguyen Thi ; Cao, Son Thanh et al. / A Heuristic Repair Algorithm for the Maximum Stable Marriage Problem with Ties and Incomplete Lists. AI 2021: Advances in Artificial Intelligence - 34th Australasian Joint Conference, AI 2021, Proceedings. editor / Guodong Long ; Xinghuo Yu ; Sen Wang. Springer Science and Business Media Deutschland GmbH, 2022. pp. 494-506 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{ef402256c5034fbd8c56b4785b36a70d,

title = "A Heuristic Repair Algorithm for the Maximum Stable Marriage Problem with Ties and Incomplete Lists",

abstract = "This paper proposes a heuristic repair algorithm to find a maximum weakly stable matching for the stable marriage problem with ties and incomplete lists. Our algorithm is designed including a well-known Gale-Shapley algorithm to find a stable matching for the stable marriage problem with ties and incomplete lists and a heuristic repair function to improve the found stable matching in terms of maximum size. Experimental results for large randomly generated instances of the problem showed that our algorithm is efficient in terms of both execution time and solution quality for solving the problem.",

keywords = "Gale-Shapley algorithm, Heuristic repair, SMTI, Stable marriage problem",

author = "Viet, \{Hoang Huu\} and Uyen, \{Nguyen Thi\} and Cao, \{Son Thanh\} and Chung, \{Tae Choong\}",

note = "Publisher Copyright: {\textcopyright} 2022, Springer Nature Switzerland AG.; 34th Australasian Joint Conference on Artificial Intelligence, AI 2021 ; Conference date: 02-02-2022 Through 04-02-2022",

year = "2022",

doi = "10.1007/978-3-030-97546-3\_40",

language = "English",

isbn = "9783030975456",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "494--506",

editor = "Guodong Long and Xinghuo Yu and Sen Wang",

booktitle = "AI 2021",

address = "Germany",

}

Viet, HH, Uyen, NT, Cao, ST & Chung, TC 2022, A Heuristic Repair Algorithm for the Maximum Stable Marriage Problem with Ties and Incomplete Lists. in G Long, X Yu & S Wang (eds), AI 2021: Advances in Artificial Intelligence - 34th Australasian Joint Conference, AI 2021, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13151 LNAI, Springer Science and Business Media Deutschland GmbH, pp. 494-506, 34th Australasian Joint Conference on Artificial Intelligence, AI 2021, Virtual, Online, 2/02/22. https://doi.org/10.1007/978-3-030-97546-3_40

A Heuristic Repair Algorithm for the Maximum Stable Marriage Problem with Ties and Incomplete Lists. / Viet, Hoang Huu; Uyen, Nguyen Thi; Cao, Son Thanh et al.
AI 2021: Advances in Artificial Intelligence - 34th Australasian Joint Conference, AI 2021, Proceedings. ed. / Guodong Long; Xinghuo Yu; Sen Wang. Springer Science and Business Media Deutschland GmbH, 2022. p. 494-506 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13151 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A Heuristic Repair Algorithm for the Maximum Stable Marriage Problem with Ties and Incomplete Lists

AU - Viet, Hoang Huu

AU - Uyen, Nguyen Thi

AU - Cao, Son Thanh

AU - Chung, Tae Choong

PY - 2022

Y1 - 2022

N2 - This paper proposes a heuristic repair algorithm to find a maximum weakly stable matching for the stable marriage problem with ties and incomplete lists. Our algorithm is designed including a well-known Gale-Shapley algorithm to find a stable matching for the stable marriage problem with ties and incomplete lists and a heuristic repair function to improve the found stable matching in terms of maximum size. Experimental results for large randomly generated instances of the problem showed that our algorithm is efficient in terms of both execution time and solution quality for solving the problem.

AB - This paper proposes a heuristic repair algorithm to find a maximum weakly stable matching for the stable marriage problem with ties and incomplete lists. Our algorithm is designed including a well-known Gale-Shapley algorithm to find a stable matching for the stable marriage problem with ties and incomplete lists and a heuristic repair function to improve the found stable matching in terms of maximum size. Experimental results for large randomly generated instances of the problem showed that our algorithm is efficient in terms of both execution time and solution quality for solving the problem.

KW - Gale-Shapley algorithm

KW - Heuristic repair

KW - SMTI

KW - Stable marriage problem

UR - https://www.scopus.com/pages/publications/85127105359

U2 - 10.1007/978-3-030-97546-3_40

DO - 10.1007/978-3-030-97546-3_40

M3 - Conference contribution

AN - SCOPUS:85127105359

SN - 9783030975456

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 494

EP - 506

BT - AI 2021

A2 - Long, Guodong

A2 - Yu, Xinghuo

A2 - Wang, Sen

PB - Springer Science and Business Media Deutschland GmbH

T2 - 34th Australasian Joint Conference on Artificial Intelligence, AI 2021

Y2 - 2 February 2022 through 4 February 2022

ER -

Viet HH, Uyen NT, Cao ST, Chung TC. A Heuristic Repair Algorithm for the Maximum Stable Marriage Problem with Ties and Incomplete Lists. In Long G, Yu X, Wang S, editors, AI 2021: Advances in Artificial Intelligence - 34th Australasian Joint Conference, AI 2021, Proceedings. Springer Science and Business Media Deutschland GmbH. 2022. p. 494-506. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-97546-3_40

A Heuristic Repair Algorithm for the Maximum Stable Marriage Problem with Ties and Incomplete Lists

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this