Improved approximation bounds for the student-project allocation problem with preferences over projects

DOI10.1016/J.JDA.2012.02.001MaRDI QIDQ450528zbMATHOpenAlexFDO

Authors Kazuo Iwama, Shuichi Miyazaki, Hiroki Yanagisawa

Publication date 13 September 2012

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2012.02.001

zbMATH Keywords

approximation algorithmNP-hardnessstable matchingapproximation ratiothe student project allocation problem

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Discrete location and assignment (90B80)

Recommendations

• Improved approximation bounds for the student-project allocation problem with preferences over projects
• A 3 / 2 -approximation Algorithm for the Student-Project Allocation Problem
• Student-project allocation with preferences over projects: algorithmic and experimental results
• Student-project allocation with preferences over projects
• Algorithms and Computation

Cites work

• scientific article; zbMATH DE number 45086 (Why is no real title available?)
• A 25/17-approximation algorithm for the stable marriage problem with one-sided ties
• Better and simpler approximation algorithms for the stable marriage problem
• College Admissions and the Stability of Marriage
• Improved approximation results for the stable marriage problem
• Student-project allocation with preferences over projects
• Two algorithms for the student-project allocation problem
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

Cited in

(11)

• Handling preferences in student-project allocation
• An integer programming approach to the student-project allocation problem with preferences over projects
• Algorithms and Computation
• A 3 / 2 -approximation Algorithm for the Student-Project Allocation Problem
• Student-project allocation with preferences over projects
• Super-stability in the student-project allocation problem with ties
• An assignment problem and its application in education domain: a review and potential path
• Student-project allocation with preferences over projects: algorithmic and experimental results
• Improved approximation bounds for the student-project allocation problem with preferences over projects
• Matchings with lower quotas: algorithms and complexity
• Profile-based optimal matchings in the student/project allocation problem

This page was built for publication: Improved approximation bounds for the student-project allocation problem with preferences over projects

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q450528)