C A L L F O R P A P E R S

===================================

Special issue of Algorithmica on

Matching Under Preferences - Algorithms and Complexity

Guest editors

-------------

Rob Irving, University of Glasgow, rwi@dcs.gla.ac.uk

Kazuo Iwama, Kyoto University, iwama@kuis.kyoto-u.ac.jp

David Manlove, University of Glasgow, davidm@dcs.gla.ac.uk

Introduction

------------

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 special issue is to explore matching problems with

preferences, with particular emphasis on the algorithms and complexity

perspective. Thus typically, papers will include results such as:

polynomial-time algorithms, NP-completeness or other complexity results,

exact (exponential-time) algorithms, parameterised algorithms, online

algorithms, approximation algorithms or inapproximability results.

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 original papers relevant to the scope

of the special issue. All submissions should be uploaded via

Springer's Online Manuscript Submission, Review and tracking System

for Algorithmica (http://www.edmgr.com/algo) where you can find

detailed information and instructions. Please note that once you

select 'Submit a Manuscript', you must choose "Matching Under

Preferences - Manlove" from the drop-down list when prompted for

'Choose Article Type'.

Deadline for submission

-----------------------

31 December 2008