Seminars & Colloquia
Brian Dean
Computer Science, Clemson University
"Recent Algorithmic Results in Stable Matching and Allocation Problems"
Wednesday February 05, 2014 11:00 AM
Location: 3211, EBII NCSU Centennial Campus
(Visitor parking instructions)
This talk is part of the Theory Seminar Series
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.
Brian C. Dean earned his PhD from MIT and is currently an Associate Professor of Computer Science in the School of Computing at Clemson University. He directs the applied algorithms research group, and has research interests spanning much of algorithmic computer science, as well as its applications in areas such as biomedical informatics, networking, scheduling, and computing education. Dr. Dean is the recipient of an NSF CAREER award as well as numerous teaching awards, and also serves as Director of the USA Computing Olympiad, one of the largest national organizations that supports advanced high-school computing education.
Host: Blair Sullivan, Computer Science, NC State University