Least-unpopularity matching criteria

Status: dormant; 2006-2008 (supersedes any conflicting remarks left on this page; see the home page for definitions)

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  I'm no longer doing this unless someone asks. ~ 2020-08-31

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.

• I studied the factor version first and proved the hardness of computing an optimal matching on May 20, 2006.  I used this work as my Senior Research Project for the Montgomery Blair High School Magnet Program and submitted it to the 2006-2007 Siemens Competition and the 2007 Intel Science Talent Search.
• In fall 2007, I began studying the margin version.  I gave a talk about the project in the University of Maryland's Capital Area Theory Seminar on September 7, 2007.
• Around September 20, 2007, I proved hardness for the margin version.  I submitted the combined work Latin American Theoretical Informatics 2008 conference, where it has been accepted.

Materials[# Top]

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.

popular-matcher software[# Top]

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.