Stability vs. Cost of Matchings

The Faculty of Informatics is pleased to announce a seminar given by Roger Wattenhofer

DATE: Tuesday, February 21st, 2012
PLACE: USI Università della Svizzera italiana, room SI-006, Informatics building (Via G. Buffi 13)
TIME: 14.30

ABSTRACT:
My talk connects two classic approaches regarding graph matchings. In his seminal 1965 paper, Jack Edmonds presented an algorithm that finds a maximum matching in a graph in polynomial time. Building upon his work, Lovasz and Plummer developed an efficient combinatorial algorithm for the weighted case, which can also be used to compute a minimum-cost perfect matching in complete graphs. In another seminal paper published a few years earlier in 1962, David Gale and Lloyd Shapley introduced the notion of a stable matching, and presented a polynomial time algorithm that computes one in a bipartite setting. Whereas Edmonds, and Lovasz and Plummer give a globally optimal solution for the matching problem, Gale and Shapley essentially compute a locally optimal solution, as no pair of nodes is unstable in the sense that they rather be matched to each other than their current partners. In my talk I will discuss whether there is a trade-off between the global and the local optimization problem. This is joint work with Yuval Emek and Tobias Langner.

BIO:
Roger Wattenhofer is a full professor at the Information Technology and Electrical Engineering Department, ETH Zurich, Switzerland. He received his doctorate in Computer Science in 1998 from ETH Zurich. From 1999 to 2001 he was in the USA, first at Brown University in Providence, RI, then at Microsoft Research in Redmond, WA. He then returned to ETH Zurich, originally as an assistant professor at the Computer Science Department. Roger Wattenhofer's research interests are a variety of algorithmic and systems aspects in computer science and information technology, currently in particular wireless networks, multi-core systems, peer-to-peer computing, and social networking. He publishes in different communities: distributed computing (e.g., PODC, SPAA, DISC), networking (e.g., MobiCom, MobiHoc,
SenSys, IPSN, HotNets), or theory (e.g., STOC, FOCS, SODA, ICALP).

HOST: Prof. Fabian Kuhn