Begum Genc

IJCAI Conference 2021 Conference Paper

Explanation in Constraint Satisfaction: A Survey

• Sharmi Dev Gupta
• Begum Genc
• Barry O'Sullivan

Much of the focus on explanation in the field of artificial intelligence has focused on machine learning methods and, in particular, concepts produced by advanced methods such as neural networks and deep learning. However, there has been a long history of explanation generation in the general field of constraint satisfaction, one of the AI's most ubiquitous subfields. In this paper we survey the major seminal papers on the explanation and constraints, as well as some more recent works. The survey sets out to unify many disparate lines of work in areas such as model-based diagnosis, constraint programming, Boolean satisfiability, truth maintenance systems, quantified logics, and related areas.

TCS Journal 2019 Journal Article

Complexity Study for the Robust Stable Marriage Problem

• Begum Genc
• Mohamed Siala
• Gilles Simonin
• Barry O'Sullivan

IJCAI Conference 2017 Conference Paper

Finding Robust Solutions to Stable Marriage

• Begum Genc
• Mohamed Siala
• Barry O'Sullivan
• Gilles Simonin

We study the notion of robustness in stable matching problems. We first define robustness by introducing (a, b)-supermatches. An (a, b)-supermatch is a stable matching in which if a pairs break up it is possible to find another stable matching by changing the partners of those a pairs and at most b other pairs. In this context, we define the most robust stable matching as a (1, b)-supermatch where b is minimum. We show that checking whether a given stable matching is a (1, b)-supermatch can be done in polynomial time. Next, we use this procedure to design a constraint programming model, a local search approach, and a genetic algorithm to find the most robust stable matching. Our empirical evaluation on large instances show that local search outperforms the other approaches.

AAAI Conference 2017 Short Paper

Robust Stable Marriage

• Begum Genc
• Mohamed Siala
• Barry O'Sullivan
• Gilles Simonin

Stable Marriage (SM) is a well-known matching problem, where the aim is to match a set of men and women. The resulting matching must satisfy two properties: there is no unassigned person and there are no other assignments where two people of opposite gender prefer each other to their current assignments. We propose a new version of SM called as Robust Stable Marriage (RSM) by combining stability and robustness. We define robustness by introducing (a, b)-supermatches, which has been inspired by (a, b)supermodels (Ginsberg, Parkes, and Roy 1998). An (a, b)supermatch is a stable matching, where if at most a pairs want to break up, it is possible to find another stable matching by breaking at most b other pairs.