Improved Approximation Bounds for the Student-Project Allocation Problem with Preferences over Projects
From MaRDI portal
Publication:3010424
DOI10.1007/978-3-642-20877-5_43zbMath1331.68091MaRDI QIDQ3010424
Hiroki Yanagisawa, Shuichi Miyazaki, Kazuo Iwama
Publication date: 1 July 2011
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-20877-5_43
90B80: Discrete location and assignment
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
91B68: Matching models
Cites Work
- Unnamed Item
- Better and simpler approximation algorithms for the stable marriage problem
- On the hardness of approximating minimum vertex cover
- Two algorithms for the student-project allocation problem
- Student-project allocation with preferences over projects
- Hard variants of stable marriage.
- 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