Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(4)
Approximate Algorithm
Capacity Constraint
Stable Matching
Student Project
Subscribe
Academic
Publications
StudentProject Allocation with Preferences over Projects
StudentProject Allocation with Preferences over Projects,David Manlove,Gregg O'malley
Edit
StudentProject Allocation with Preferences over Projects
(
Citations: 6
)
BibTex

RIS

RefWorks
Download
David Manlove
,
Gregg O'malley
We study the problem of allocating students to projects, where both stu dents and lecturers have preferences over projects, and both projects and lec turers have capacities. In this context we seek a
stable matching
of students to projects, which respects these preference and capacity constraints. Here, the stability definition generalises the corresponding notion in the context of the classical Hospitals / Residents problem. We show that stable matchings can have dierent sizes, and the problem of finding a maximum cardinality
stable matching
is NPhard, though approximable within a factor of 2.
Conference:
Algorithms and Complexity in Durham  ACID
, pp. 6980, 2005
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.dcs.gla.ac.uk
)
Citation Context
(6)
...Abstract—Student project allocations models (SPA) in which lecturers have preferences over students (projects) have been studied in [
2
, 3]. We present new method to construct a general student project allocation model (SPA(s, p)) in which the lecturers have preference lists over pairs (student, project), and the students have preference lists over projects...
...Manlove and O’Malley [
2
] presented a model for the student project allocation with preference lists over projects denoted SPAP...
...In 2005, D. F. Manlove and G. O’Malley [
2
] gave a student project allocation with preference over projects (SPAP)...
...The authors in [1,
2
] notes that a new model over (student, project) pairs may improve the results of the problem...
... lଵ offers the projects pଵ pଶ and pଷ. Each project has capacity 1, whilst lଵ has capacity 2. The student sଵ prefers the project pଷ to the project pଵ and the student sଶ prefers the project pଷ to the project pଶ. This instance has two stable matching Mଵ ൌሼ ሺ sଵ ,p ଷሻ ሺ sଶ ,p ଶሻ ሽ and Mଶ ൌሼ ሺ sଵ ,p ଵሻ ሺ sଶ ,p ଷሻ ሽ . It is clearly that Mଶ is better than Mଵ but in that model it is NP problem to find best matching, the authors of SPAp models [
2
] ...
Ahmed H. Abu ElAtta
,
et al.
Student Project Allocation with Preference Lists over (Student, Projec...
...(Given a graph G, the subdivision graph of G, denoted by S(G), is obtained by subdividing each edge fu; wg of G in order to obtain two edges fu; vg and fv; wg of S(G), where v is a new vertex.) It turns out that exactmm is NPcomplete for the same class of graphs [
20
]...
Robert W. Irving
,
et al.
The stable marriage problem with master preference lists
...We have considered this model from an algorithmic viewpoint—see [
16
] for further details...
David J. Abraham
,
et al.
Two algorithms for the StudentProject Allocation problem
...Proof. Clearly comsmsym is in NP. To show NPhardness, we reduce from exactmm in subdivision graphs, which is NPcomplete [
21
]...
David J. Abraham
,
et al.
The Stable Roommates Problem with GloballyRanked Pairs
...We have considered this model from an algorithmic viewpoint ‐ see [
17
] for further details...
David J. Abraham
,
et al.
The StudentProject Allocation Problem
References
(13)
The StudentProject Allocation Problem
(
Citations: 7
)
David J. Abraham
,
Robert W. Irving
,
David F. Manlove
Conference:
International Symposium on Algorithms and Computation  ISAAC
, pp. 474484, 2003
Student project allocation using integer programming
(
Citations: 8
)
A. A. Anwar
,
A. S. Bahaj
Journal:
IEEE Transactions on Education  IEEE TRANS EDUC
, vol. 46, no. 3, pp. 359367, 2003
College admissions and the stability of marriage
(
Citations: 1234
)
D. Gale
,
L. S. Shapley
Published in 1962.
The stable marriage problem: structures and algorithms
(
Citations: 138
)
Dan Gusfield
,
Robert W. Irving
Published in 1989.
Approximability results for stable marriage problems with ties
(
Citations: 28
)
Magnús M. Halldórsson
,
Robert W. Irving
,
Kazuo Iwama
,
David F. Manlove
,
Shuichi Miyazaki
,
Yasufumi Morita
,
Sandy Scott
Journal:
Theoretical Computer Science  TCS
, vol. 306, no. 13, pp. 431447, 2003
Sort by:
Citations
(6)
Student Project Allocation with Preference Lists over (Student, Project) Pairs
Ahmed H. Abu ElAtta
,
M. I. Moussa
Conference:
International Conference on Computer and Electrical Engineering  ICCEE
, 2009
The stable marriage problem with master preference lists
(
Citations: 6
)
Robert W. Irving
,
David F. Manlove
,
Sandy Scott
Journal:
Discrete Applied Mathematics  DAM
, vol. 156, no. 15, pp. 29592977, 2008
Two algorithms for the StudentProject Allocation problem
(
Citations: 10
)
David J. Abraham
,
Robert W. Irving
,
David F. Manlove
Journal:
Journal of Discrete Algorithms  JDA
, vol. 5, no. 1, pp. 7390, 2007
The Stable Roommates Problem with GloballyRanked Pairs
(
Citations: 8
)
David J. Abraham
,
Ariel Levavi
,
David F. Manlove
,
Gregg O’Malley
Journal:
Internet Mathematics
, vol. 5, no. 4, pp. 431444, 2007
The StudentProject Allocation Problem
(
Citations: 7
)
David J. Abraham
,
Robert W. Irving
,
David F. Manlove
Conference:
International Symposium on Algorithms and Computation  ISAAC
, pp. 474484, 2003