# The Roommates Problem

### Ethan Bernstein and Sridhar Rajagaopalan

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/CSD-93-757

1993

### http://www.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://www.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://www.eecs.berkeley.edu/Pubs/TechRpts/1993/6282.html %F Bernstein:CSD-93-757