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

DOI10.1016/j.jda.2012.02.001zbMath1252.68142OpenAlexW2055987334MaRDI QIDQ450528

Shuichi Miyazaki, Kazuo Iwama, 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) Discrete location and assignment (90B80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (6)

Profile-Based Optimal Matchings in the Student/Project Allocation Problem ⋮ Matchings with lower quotas: algorithms and complexity ⋮ Handling preferences in student-project allocation ⋮ An assignment problem and its application in education domain: a review and potential path ⋮ Super-stability in the student-project allocation problem with ties ⋮ Student-project allocation with preferences over projects: algorithmic and experimental results

Cites Work

• Unnamed Item
• Better and simpler approximation algorithms for the stable marriage problem
• Two algorithms for the student-project allocation problem
• Student-project allocation with preferences over projects
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Improved approximation results for the stable marriage problem
• A 25/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties
• College Admissions and the Stability of Marriage

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