|
MATCH-UP: Matching Under Preferences |
– Algorithms
and Complexity |
|
Satellite workshop
of ICALP 2008 |
|
|
|
|
|
|
|
Dedicated
to the memory of David Gale,
13 December 1921 - 7 March 2008 |
|
|
Matching problems with preferences occur in
widespread applications such as the assignment of school-leavers to
universities, junior doctors to hospitals, students to campus housing,
children to schools, kidney transplant patients to donors and so on. The common thread is that individuals
have preference lists over the
possible outcomes and the task is to find a matching
of the participants that is in some sense optimal
with respect to these preferences. The remit of this workshop is to explore matching problems
with preferences with an emphasis on the algorithms and complexity
perspective, but a key objective is also to bring together the computer
science and economics communities who have tended to follow different paths
when studying these problems previously.
Further background information about the workshop is
available. |
|
Invited
speakers ·
Kurt Mehlhorn, Max Planck Institut fűr Informatik o Seminar title: “Assigning papers to
reviewers” o
Seminar title: “Kidney exchange: design
and evolution of a computer-assisted matching mechanism” ·
Marilda Sotomayor, Universidade de São
Paolo o
Seminar title: “My encounters with David
Gale” |
List of
topics The
matching problems under consideration include, but are not limited to: |
|
· |
bipartite matching problems with preference lists on both
sides,
where a matching is optimal if it is: o
stable – this includes variants of the stable
marriage and hospitals / residents problems; o
rank-maximal (or otherwise optimal with respect to
matching profile), minimum cost, popular or Pareto optimal. |
· |
bipartite matching problems with preferences on one side (includes house
allocation / job matching / student-project allocation), where a matching is
optimal if it is: o
rank-maximal (or otherwise optimal with respect to
matching profile), minimum cost, popular or Pareto optimal. |
· |
non-bipartite matching problems with preferences (includes kidney
exchange / chess tournament problems), where a matching is optimal if it is: o
stable – this includes variants of the stable
roommates problem; o
rank-maximal (or otherwise optimal with respect to
matching profile), minimum cost, popular or Pareto optimal. |
Submissions Authors are invited to submit papers focussing on aspects of
matching problems with preferences that are of relevance to the
workshop. Such a paper can either
(i) be based on original results that have not been published previously, or
(ii) survey existing results that have already appeared in the literature
(provided that the majority of the survey text has not itself been published
previously). Submissions should be at most 12 pages in length, using
11-point font or greater, on A4 or US-letter paper with at least 1-inch
margins round the text. Papers
will be selected according to (a) relevance to the workshop, (b) originality,
significance and rigour (in the case of type (i) papers), and (c) interest to
the community and coverage of the literature (in the case of type (ii)
papers). Submissions should be sent by email attachment to matchup@dcs.gla.ac.uk. Accepted
papers will be disseminated via the workshop website and informal working
notes to be distributed at the workshop – this should not prevent the
simultaneous or subsequent submission of contributed papers to other
workshops, conferences or journals.
At least one author of each accepted paper must attend the workshop in
order to present the paper. Authors
of selected accepted papers will be invited to submit their papers to a special issue of Algorithmica. Accepted
papers The
accepted papers are available here. Workshop
programme The
workshop programme is available here. Workshop
proceedings The
informal working notes (6.5Mb) distributed at the workshop can be downloaded
from here. Workshop
photos Some
photos from the day itself can be viewed here. Important
dates Deadline
for submission of contributed papers: Notification
of acceptance: Final
version for working notes due: Workshop:
Organising
committee ·
Magnús M.
Halldórsson, ·
Rob Irving, ·
Kazuo Iwama, ·
David Manlove, Registration Click
here for information about how to
register for this workshop. It is
not necessary to register for the main ICALP conference in order to
participate in this event. Further
information e-mail: matchup@dcs.gla.ac.uk |
||
|
|
|
|
|
|
We gratefully acknowledge
financial support from the following sources: School of Informatics, Kyoto University |