The Roommates Problem

Ethan Bernstein and Sridhar Rajagaopalan

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-93-757
1993

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/CSD-93-757.pdf

We consider a version of on-line maximum matching where an edge may be matched when either endpoint arrives. In contrast with previous work, we work with general undirected graphs with arbitrary edge weights. Our algorithms are inspired by the maxim "A bird in the hand is worth two in the bush". For the weighted case, we give a deterministic algorithm with a worst-case performance ratio of ${1 \over 4}$. We prove an upper bound on the worst case performance ratio of any deterministic on-line algorithm of ${1 \over 3}$. For the unweighted case, we prove a tight bound of ${2 \over 3}$ on the possible worst-case performance ratio of any deterministic on-line algorithm. All running times are small polynomials ($O(\size{V}\cdot\size{E})$) using naive implementations and no complicated data structures. As justified by previous work, problems of this nature are of practical importance.


BibTeX citation:

@techreport{Bernstein:CSD-93-757,
    Author = {Bernstein, Ethan and Rajagaopalan, Sridhar},
    Title = {The Roommates Problem},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1993},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/6282.html},
    Number = {UCB/CSD-93-757},
    Abstract = {We consider a version of on-line maximum matching where an edge may be matched when either endpoint arrives. In contrast with previous work, we work with general undirected graphs with arbitrary edge weights. Our algorithms are inspired by the maxim "A bird in the hand is worth two in the bush". For the weighted case, we give a deterministic algorithm with a worst-case performance ratio of ${1 \over 4}$.  We prove an upper bound on the worst case performance ratio of any deterministic on-line algorithm of ${1 \over 3}$.  For the unweighted case, we prove a tight bound of ${2 \over 3}$ on the possible worst-case performance ratio of any deterministic on-line algorithm. All running times are small polynomials ($O(\size{V}\cdot\size{E})$) using naive implementations and no complicated data structures. As justified by previous work, problems of this nature are of practical importance.}
}

EndNote citation:

%0 Report
%A Bernstein, Ethan
%A Rajagaopalan, Sridhar
%T The Roommates Problem
%I EECS Department, University of California, Berkeley
%D 1993
%@ UCB/CSD-93-757
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/6282.html
%F Bernstein:CSD-93-757