Improved approximation bounds for the student-project allocation problem with preferences over projects
From MaRDI portal
Publication:450528
DOI10.1016/j.jda.2012.02.001zbMath1252.68142MaRDI 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
approximation algorithm; NP-hardness; stable matching; approximation ratio; the student project allocation problem
90C59: Approximation methods and heuristics in mathematical programming
90B80: Discrete location and assignment
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms
Related Items
Super-stability in the student-project allocation problem with ties, An assignment problem and its application in education domain: a review and potential path, Matchings with lower quotas: algorithms and complexity, Handling preferences in student-project allocation, Student-project allocation with preferences over projects: algorithmic and experimental results, Profile-Based Optimal Matchings in the Student/Project Allocation Problem
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