Date(s) - 15/10/2019
1:00 pm - 2:00 pm
School of Computing Science
SICSA DVF Professor Esra Erdam, Professor in Computer Science and Engineering at Sabanci University will be giving a FATA talk on ‘A General Framework for Stable Roommate Problems’ at the University of Glasgow on 15th October.
The Stable Roommate problem (SR) is characterized by the preferences of agents over other agents as roommates: each agent ranks all others in strict order of preference. A solution to SR is then a partition of the agents into pairs so that each pair shares a room, and there is no pair of agents that would block this matching (i.e., who prefers the other to their roommate in the matching). There are interesting variations of SR that are computationally hard. For instance, SRI considers incomplete preferences, Egalitarian SRI further tries to maximize the total satisfaction of preferences of all agents, and Almost SRI tries to minimize the total number of blocking pairs. We introduce a formal framework that is general enough to solve many of such variations of SR declaratively. This framework is based on Answer Set Programming (ASP) — a rich knowledge representation and reasoning paradigm with an expressive formalism and efficient solvers.
Esra Erdem is an associate professor in computer science and engineering at Sabanci University. She received her Ph.D. in computer sciences at the University of Texas at Austin (2002), and carried out postdoctoral research at the University of Toronto and Vienna University of Technology from 2002 to 2006. Her research is in the area of artificial intelligence, in particular, the mathematical foundations of knowledge representation and reasoning, and their applications to cognitive robotics and computational biology.