Matt McCutchen's Web SiteLeast-Unpopularity Matching Criteria  (Top, Materials, popular-matcher software, Bottom).  Email me about this page.

Least-Unpopularity Matching Criteria

I plan to post a corrected, maintained author's version of the LATIN 2008 paper and slides soon.  In the meantime, you can get the published version of the paper from Springer if you have a subscription.  I regret the delay. -- Matt 2008-05-17

This is a computer science research project I completed under the advice of Dr. Samir Khuller of the University of Maryland.  I defined and studied the least-unpopularity-factor and least-unpopularity-margin optimality criteria for matching based on one-sided preferences and showed that, under either criterion, it is NP-hard to compute an optimal matching.

Materials

Two papers about this work are available here: the LUMC paper, which covers both the factor and margin criteria for a computer science audience, and the LUFM paper, which covers only the factor criterion but has an introduction accessible to a more general audience.  In addition, my slides from the CATS talk are available in OpenOffice.org and PDF formats. Note: The copyright to the LUMC paper now belongs to Springer.

DescriptionFileSizeModification time
LUMC paper (complete)lumc.pdf1609782007-09-27 20:46:49 +0000
LUFM paper (gentler introduction)lufm.pdf1602212007-03-11 20:37:53 +0000
CATS talk slides (OpenOffice.org)cats-talk-slides.odp641502007-09-06 23:35:09 +0000
CATS talk slides (PDF)cats-talk-slides.pdf4772302007-09-06 23:35:29 +0000

popular-matcher software

As I did my research, I found it very helpful to implement the algorithms and calculations that I considered on the computer so I could run experiments.  As a result, I have accumulated a program called the popular-matcher consisting of a set of Java classes that implement the algorithms to calculate the unpopularity factor and margin, the conversion from 3SAT instances to matching problems, and various other calculations I found useful.  I made no effort to make the code pretty or well-designed, only to make it work for my purposes.  I am now offering the popular-matcher for download in case others find it helpful to see implementations of the algorithms or want to run their own experiments.

Last updated 2007-09-26: Initial posting.

FileSizeModification time
popular-matcher.zip1090352007-09-27 01:46:34 +0000

Matt McCutchen's Web SiteLeast-Unpopularity Matching Criteria  (Top, Materials, popular-matcher software, Bottom).  Email me about this page.
Modification time of this page's main source file: 2009-05-06 04:15:11 +0000
Except where otherwise noted, Matt McCutchen waives his copyright to the content of this site.  This site comes with absolutely no warranty.  Why?