Sunday, September 14, 2008


Maximum weighted bipartite matching is a well-known optimization problem. Inspired (loosely) by its emergence in sponsored search, researchers have studied their exploration + exploitation versions where nodes or edges may arrive in some order and some weights are observed before committing to the matching (eg., as in graph secretary problems).

I would like to see similar formulations for the well-known stable marriages problem. This formulation should consider the gradual revealing of preferences. What FOCS/STOC/SODA style formulation will lead to pretty math and powerful technical results, motivations entirely aside?


Anonymous Anonymous said...

Samir Khuller had a paper on online stable marriage that appeared ICALP years ago.

1:02 PM  

Post a Comment

<< Home