Introduction

In Matchings with One Sided Preferences we are given a bipartite graph $G(V,E)$ where $V = \mathcal{A} \cup \mathcal{P}$ . Set $\mathcal{A}$ denotes a set of applicants and set $\mathcal{P}$ of posts. Each applicant in $\mathcal{A}$ submits a preference list (a ranking of a subset of the posts, possibly including ties). Edges which are choice $i$ are called rank $i$ edges.

Given this setting we may ask for matchings which satisfy different optimization criteria. This library contains code for the two following such criteria.

Rank-Maximal Matchings

A rank-maximal matching is a matching which contains the maximum number of first choice edges. Given that constraint it contains the maximum number of second choice edges and so on. A rank-maximal matching can be computed in polynomial time. libMOSP contains three implementations which compute such a matching:

An $O( \min(n+r, r \sqrt{n} ) m )$ algorithm where is the maximum rank of an edge in the instance. See here for a description of the algorithm.
An algorithm with the same running time but based on a different approach (reducing the problem to the weighted matching problem). See here for more details.
Again an algorithm which reduces the problem to the weighted matching but this time with slower running time $O( n^2 ( m + n \log n ) )$ and more space . The extra comes from the possible cost of arithmetic since the algorithm handles numbers up to .

Except for the above, libMOSP contains an implementation of a rank-maximal matching algorithm with capacities. In this case the nodes of the right-side partition of the bipartite graph may have capacities larger that 1, i.e. they may be matched more than once. The library contains:

An algorithm. See here for more details.

Popular Matchings

We say that a matching $M'$ is more popular than matching $M$ if more applicants prefer $M'$ than those who prefer $M$ . Applicants who are indifferent are ignored. A matching $M$ is popular if there is no other matching which is more popular.

Popular matchings can also be computed in polynomial time (see here for more details), but unfortunately they do not always exist. In that case we wish to compute matchings which approximate the least unpopular matching (see here for more details).

libMOSP contains two algorithms.

An $O( \sqrt{n} m )$ algorithm from here which decides if the instance has a popular matching or not (and possibly returns one).
An algorithm which is a variation of the previous one and is guarantied to return a result even if the instance does not admit a popular matching. See here for a more detailed description.

libMOSP also provides routines to compute the so called "unpopularity factor" and the "unpopularity margin" of a matching (see McCutchen 2007).

Generators

The library also contains 4 random structured instance generators.

Requirements

This implementation is written in C++ and uses LEDA. The structure of the package follows that of a LEDA extension package (LEP).

Supported Platforms

This package has been tested on the following platforms:

gcc 3.x, 4.0.x and 4.1.x under Linux
gcc 3.x under SunOS 5.9
gcc 3.x under Cygwin

but it may work on others too.

License

 This program can be freely used in an academic environment
 ONLY for research purposes, subject to the following restrictions:

 1. The origin of this software must not be misrepresented; you must not
    claim that you wrote the original software. If you use this software
    an acknowledgment in the product documentation is required.
 2. Altered source versions must be plainly marked as such, and must not be
    misrepresented as being the original software.
 3. This notice may not be removed or altered from any source distribution.

 Any other use is strictly prohibited by the author, without an explicit
 permission.

 This software is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Note that this package uses LEDA, which is not free.

News

01 Feb 2010: v0.7 released
- Added implementation of popular matchings and variations
- Added random structures instance generators
- Support LEDA 6.0 on linux platforms.
24 Apr 2005: v0.6 released
- Support LEDA 5.0 on win32 platforms with bcc32
23 Feb 2005: v0.5 released
- Support Borland C++ bcc32 (only LEDA 4.5 or earlier)
- Minor fixes
11 Feb 2005: v0.3 released
- Support for LEDA-5.0 added, see INSTALL file
19 Oct 2004: v0.2 released
23 Sep 2004: v0.1 released containing implementation of rank-maximal matchings

Download

Source package (v0.7). [tar.gz]
Source package (v0.6). [tar.gz]
Source package (v0.5). [tar.gz]
Source package (v0.3). [tar.gz]
Source package (v0.2). [tar.gz]

Source

The repository can be found at github.

Code Example

Rank-Maximal Matchings

#include <LEP/mosp/mosp.h>
int main() {
    leda::graph G;
    // construct simple, loopfree, bipartite graph G 
    leda::edge_array<int> rank(G, 1);
    // fill up ranks
    leda::list< leda::edge > M = mosp::BI_RANK_MAX_MATCHING( G, rank );
    // do something with M
    return 0;
} 

Popular Matchings

#include <LEP/mosp/mosp.h>
int main() {
     leda::graph G;
     // construct simple, loopfree, bipartite graph G 
     leda::list< leda::node > A, B;
     // add left partition nodes to A, right partition nodes to B
     leda::edge_array<int> rank(G, 1);
     // fill up ranks
     leda::list< leda::edge > M;
     bool is_popular = mosp::BI_POPULAR_MATCHING( G, A, B, rank, M );
         // do something with M
     return 0;
}

Popular Approximation

#include <LEP/mosp/mosp.h>
int main() {
    leda::graph G;
    // construct simple, loopfree, bipartite graph G 
    leda::list< leda::node > A, B;
    // add left partition nodes to A, right partition nodes to B
    leda::edge_array<int> rank(G, 1);
    // fill up ranks
    int phase;
    leda::list< leda::edge > M;
    bool is_popular = mosp::BI_APPROX_POPULAR_MATCHING( G, A, B, rank, M, phase );
    int unpopularity_factor;
    if ( mosp::BI_UNPOPULARITY_FACTOR( G, A, B, rank, M, unpopularity_factor ) )
            std::cout << "unpopularity factor = " << unpopularity_factor << std::endl;
        // do something with M
    return 0;
} 