Recent Algorithmic Results in Stable Matching and Allocation Problems

Brian C. Dean ( Clemson University )

Matchings are a well-studied class of problems in algorithmic computer science, where we must find an assignment (e.g., jobs to machines) that is optimal in some sense, for example maximum cardinality or minimum cost. In this talk, I will discuss ordinal matching problems, where the input consists of ranked preference lists instead of explicit numeric costs (e.g., a job might prefer to be assigned to one machine over another). The best-known problem in this domain is the classical stable marriage problem, where we want to find a matching between N men and N women, such that there exists no unmatched (man, woman) pair preferring each-other to their partners in the matching. A natural generalization of this problem is the stable allocation problem, where we assign elements that are all potentially of different sizes; for example, we might assign jobs of varying size to machines of varying capacity. I’ll discuss several of our recent algorithmic results for problems in this general domain, focusing mainly on fast algorithms for solving stable allocation problems and “unsplittable” stable allocation problems.