Modeling stable matching problems with answer set programming

De Clercq, Sofie, Schockaert, Steven ORCID: https://orcid.org/0000-0002-9256-2881, De Cock, Martine and Nowé, Ann 2013. Modeling stable matching problems with answer set programming. Presented at: 7th International Symposium, RuleML 2013, Seattle, USA, 11-13 July 2013. Published in: Morgenstern, L., Stefaneas, P., Levy, F., Wyner, A. and Paschke, A. eds. Theory, Practice, and Applications of Rules on the Web: 7th International Symposium, RuleML 2013, Seattle, WA, USA, July 11-13, 2013. Proceedings. Lecture Notes in Computer Science. Lecture Notes in Computer Science , vol.8035 Berlin: Springer, pp. 68-83. 10.1007/978-3-642-39617-5_10

Full text not available from this repository.

Abstract

The Stable Marriage Problem (SMP) is a well-known matching problem first introduced and solved by Gale and Shapley [7]. Several variants and extensions to this problem have since been investigated to cover a wider set of applications. Each time a new variant is considered, however, a new algorithm needs to be developed and implemented. As an alternative, in this paper we propose an encoding of the SMP using Answer Set Programming (ASP). Our encoding can easily be extended and adapted to the needs of specific applications. As an illustration we show how stable matchings can be found when individuals may designate unacceptable partners and ties between preferences are allowed. Subsequently, we show how our ASP based encoding naturally allows us to select specific stable matchings which are optimal according to a given criterion. Each time, we can rely on generic and efficient off-the-shelf answer set solvers to find (optimal) stable matchings.

Item Type:	Conference or Workshop Item (Paper)
Date Type:	Publication
Status:	Published
Schools:	Computer Science & Informatics
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Publisher:	Springer
ISBN:	9783642396168
ISSN:	0302-9743
Last Modified:	27 Oct 2022 10:01
URI:	https://orca.cardiff.ac.uk/id/eprint/68598

Citation Data

Cited 3 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item