Improved approximation bounds for the student-project allocation problem with preferences over projects
DOI10.1016/J.JDA.2012.02.001zbMATH Open1252.68142OpenAlexW2055987334MaRDI QIDQ450528FDOQ450528
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
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
approximation algorithmNP-hardnessstable matchingapproximation ratiothe student project allocation problem
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)
Cites Work
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Improved approximation results for the stable marriage problem
- Title not available (Why is that?)
- College Admissions and the Stability of Marriage
- Two algorithms for the student-project allocation problem
- Student-project allocation with preferences over projects
- A 25/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties
- Better and simpler approximation algorithms for the stable marriage problem
Cited In (9)
- Handling preferences in student-project allocation
- Profile-Based Optimal Matchings in the Student/Project Allocation Problem
- An assignment problem and its application in education domain: a review and potential path
- Super-stability in the student-project allocation problem with ties
- A 3 / 2 -approximation Algorithm for the Student-Project Allocation Problem
- Student-project allocation with preferences over projects
- Algorithms and Computation
- Student-project allocation with preferences over projects: algorithmic and experimental results
- Matchings with lower quotas: algorithms and complexity
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)
