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

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

zbMATH Keywords

approximation algorithmNP-hardnessstable matchingapproximation ratiothe student project allocation problem

Mathematics Subject Classification ID

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