Second Call for Papers for ICALP 2008 workshop: MATCH-UP
Professor David Gale had kindly agreed to open the above workshop with
a historical perspective on the field of matching problems. After
hearing the sad news of his death on 7 March 2008, we have arranged in
consultation with his family to honour his life and work during the
course of the day, and details of how we intend to do this are included
below.
Second call for papers
MATCH-UP: Matching Under Preferences
- Algorithms and Complexity
Satellite workshop of ICALP 2008
6 July 2008
Reykjavik, Iceland
http://www.dcs.gla.ac.uk/research/algorithms/workshop
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.
Invited speakers
—————-
* Kurt Mehlhorn, Max Planck Institut fur Informatik
* Al Roth, Harvard University
* Marilda Sotomayor, Universidade de Sao Paolo
- who will describe the contribution of David Gale to the theory of
matching problems
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:
- stable - this includes variants of the stable marriage and
hospitals / residents problems;
- 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:
- 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:
- stable - this includes variants of the stable roommates problem;
- 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.
Authors of selected accepted papers will be invited to submit their
papers to a special issue of Algorithmica.
Important dates
—————
Submission of contributed papers: 3 May 2008
Notification of acceptance: 1 June 2008
Final version for working notes due: 10 June 2008
Workshop: 6 July 2008
Organising committee
——————–
* Magnus Halldorsson, Reykjavik University
* Rob Irving, University of Glasgow
* Kazuo Iwama, Kyoto University
* David Manlove, University of Glasgow
Further information
——————-
See http://www.dcs.gla.ac.uk/research/algorithms/workshop